{"id":"informatyka-2017-maj-matura-rozszerzona/zad/6.4","paper_id":"informatyka-2017-maj-matura-rozszerzona","number":"6.4","points":4,"ptype":"open","subject":"informatyka","category":"matura","year":2017,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 6.1.\n\nPodaj długość najdłuższej linii pionowej (czyli ciągu kolejnych pikseli w tej samej kolumnie obrazka), złożonej z pikseli tej samej jasności.\n\nDla danych z pliku przyklad.txt wynikiem jest 198.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Najdłuższa linia pionowa o jednolitej jasności: 5 pikseli** (w `dane.txt`).\n\nDla `przyklad.txt`: 198.\n\nDla każdej kolumny przeglądamy wszystkie 200 wierszy z góry na dół i utrzymujemy aktualną długość ciągu identycznych wartości (\"streak\"). Wynikiem jest globalne maksimum tych streaków.\n\n## Sposób 1 - Python (najczytelniejszy)\n\n```python\n# Wczytaj obraz jako macierz [200][320]\nwith open('dane.txt') as f:\nobraz = [[int(x) for x in linia.split()] for linia in f]\n\nW, K = len(obraz), len(obraz[0]) # 200, 320\nmax_dl = 1\n\nfor c in range(K):\nbiezacy = 1\nfor r in range(1, W):\nif obraz[r][c] == obraz[r-1][c]:\nbiezacy += 1\nif biezacy > max_dl:\nmax_dl = biezacy\nelse:\nbiezacy = 1\n\nprint(max_dl) # 5\n\n## Sposób 2 - C++ (kolumna-po-kolumnie)\n\n```cpp\n#include \n#include \nusing namespace std;\n\nconst int W = 200, K = 320;\nint obraz[W][K];\n\nint main() {\nifstream plik(\"dane.txt\");\nfor (int r = 0; r < W; r++)\nfor (int c = 0; c < K; c++)\nplik >> obraz[r][c];\nint max_dl = 1;\nfor (int c = 0; c < K; c++) {\nint biezacy = 1;\nfor (int r = 1; r < W; r++) {\nif (obraz[r][c] == obraz[r-1][c]) {\nbiezacy++;\nif (biezacy > max_dl) max_dl = biezacy;\n} else {\nbiezacy = 1;\n}\n}\n}\ncout << max_dl << endl; // 5\nreturn 0;\n}\n\n## Sposób 3 - Pascal\n\n```pascal\nprogram NajdluzszaLinia;\nvar\nobraz: array[1 200, 1 320] of Integer;\nr, c, biezacy, max_dl: Integer;\nf: TextFile;\nbegin\nAssignFile(f, 'dane.txt'); Reset(f);\nfor r := 1 to 200 do\nfor c := 1 to 320 do Read(f, obraz[r, c]);\nCloseFile(f);\nmax_dl := 1;\nfor c := 1 to 320 do\nbegin\nbiezacy := 1;\nfor r := 2 to 200 do\nif obraz[r, c] = obraz[r-1, c] then\nbegin\nInc(biezacy);\nif biezacy > max_dl then max_dl := biezacy;\nend\nelse\nbiezacy := 1;\nend;\nWriteln(max_dl); // 5\nend.\n\n## Reference algorytmiczny - najdłuższy podciąg jednakowych\n\n> Reference - Run-Length Encoding (najdłuższy run):\n> - Przeglądaj sekwencję jeden raz, utrzymując zmienną \"biezacy\" liczącą długość bieżącego ciągu.\n> - Gdy element się ZMIENIA, resetuj biezacy = 1; gdy się POWTARZA, zwiększaj.\n> - Po każdym kroku aktualizuj globalne maksimum.\n> - Złożoność: O(n) na sekwencję.\n> - Dla obrazu 200×320 = 64 000 pikseli: O(W · K) = O(64 000) operacji. Szybko.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 6.4, max 4 pkt):\n> - **4 pkt** - prawidłowa odpowiedź: **5**.\n> - **2 pkt** - odpowiedź **4** lub **6** (off-by-one error: liczone końce/granice przedziału lub błędna inicjalizacja).\n> - **0 pkt** - inna błędna odpowiedź lub brak.\n> - **UWAGA:** Nie przyznaje się 3 pkt i 1 pkt.\n\n## Typowe pułapki\n\n- **Liczenie linii POZIOMYCH zamiast PIONOWYCH** - pionowa = w tej samej KOLUMNIE, idziemy w dół. Częsta pomyłka kierunku iteracji.\n- **Inicjalizacja biezacy = 0 vs 1** - pierwszy piksel zaczyna ciąg, więc biezacy = 1. Inicjalizacja = 0 da off-by-one (odpowiedź 4 lub 6 zamiast 5).\n- **Reset biezacy = 0 zamiast 1** - gdy element zmienia się, nowa wartość zaczyna NOWY ciąg długości 1, nie 0.\n- **Brak aktualizacji max_dl PRZY PIERWSZYM piksele** - można pomylić i pominąć kolumny gdzie wszystkie 200 pikseli są takie same. Inicjalizacja max_dl = 1 lub aktualizacja po każdej iteracji.\n- **Indeksowanie 0 vs 1** - w Pascalu od 1, w Python/C++ od 0. Pętla wewnętrzna `for r in range(1, W)` (Python) lub `for r := 2 to 200` (Pascal).\n- **dane.txt vs przyklad.txt** - przyklad zwraca 198 (prawie cała kolumna), dane.txt tylko 5 (obraz różnorodny).\n\n## Złożoność obliczeniowa\n\n- Wczytanie: O(W × K) = O(64 000).\n- Główna pętla: O(W × K) = O(64 000) operacji.\n- **Całkowita: O(W × K)**, liniowa względem rozmiaru obrazu.\n- Pamięć: O(W × K) na macierz lub O(W) (jednej kolumny naraz, gdyby trzymać tylko bieżącą kolumnę).","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2017 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 6.1.

\n

Podaj długość najdłuższej linii pionowej (czyli ciągu kolejnych pikseli w tej samej kolumnie obrazka), złożonej z pikseli tej samej jasności.

\n

Dla danych z pliku przyklad.txt wynikiem jest 198.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Najdłuższa linia pionowa o jednolitej jasności: 5 pikseli (w dane.txt).

\n

Dla przyklad.txt: 198.

\n

Dla każdej kolumny przeglądamy wszystkie 200 wierszy z góry na dół i utrzymujemy aktualną długość ciągu identycznych wartości ("streak"). Wynikiem jest globalne maksimum tych streaków.

\n

Sposób 1 - Python (najczytelniejszy)

\n

```python

\n

Wczytaj obraz jako macierz [200][320]

\n

with open('dane.txt') as f:
obraz = [[int(x) for x in linia.split()] for linia in f]

\n

W, K = len(obraz), len(obraz[0]) # 200, 320
max_dl = 1

\n

for c in range(K):
biezacy = 1
for r in range(1, W):
if obraz[r][c] == obraz[r-1][c]:
biezacy += 1
if biezacy > max_dl:
max_dl = biezacy
else:
biezacy = 1

\n

print(max_dl) # 5

\n

Sposób 2 - C++ (kolumna-po-kolumnie)

\n

```cpp
#include <iostream>
#include <fstream>
using namespace std;

\n

const int W = 200, K = 320;
int obraz[W][K];

\n

int main() {
ifstream plik("dane.txt");
for (int r = 0; r < W; r++)
for (int c = 0; c < K; c++)
plik >> obraz[r][c];
int max_dl = 1;
for (int c = 0; c < K; c++) {
int biezacy = 1;
for (int r = 1; r < W; r++) {
if (obraz[r][c] == obraz[r-1][c]) {
biezacy++;
if (biezacy > max_dl) max_dl = biezacy;
} else {
biezacy = 1;
}
}
}
cout << max_dl << endl; // 5
return 0;
}

\n

Sposób 3 - Pascal

\n

```pascal
program NajdluzszaLinia;
var
obraz: array[1 200, 1 320] of Integer;
r, c, biezacy, max_dl: Integer;
f: TextFile;
begin
AssignFile(f, 'dane.txt'); Reset(f);
for r := 1 to 200 do
for c := 1 to 320 do Read(f, obraz[r, c]);
CloseFile(f);
max_dl := 1;
for c := 1 to 320 do
begin
biezacy := 1;
for r := 2 to 200 do
if obraz[r, c] = obraz[r-1, c] then
begin
Inc(biezacy);
if biezacy > max_dl then max_dl := biezacy;
end
else
biezacy := 1;
end;
Writeln(max_dl); // 5
end.

\n

Reference algorytmiczny - najdłuższy podciąg jednakowych

\n
Reference - Run-Length Encoding (najdłuższy run):
- Przeglądaj sekwencję jeden raz, utrzymując zmienną "biezacy" liczącą długość bieżącego ciągu.
- Gdy element się ZMIENIA, resetuj biezacy = 1; gdy się POWTARZA, zwiększaj.
- Po każdym kroku aktualizuj globalne maksimum.
- Złożoność: O(n) na sekwencję.
- Dla obrazu 200×320 = 64 000 pikseli: O(W · K) = O(64 000) operacji. Szybko.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 6.4, max 4 pkt):
- 4 pkt - prawidłowa odpowiedź: 5.
- 2 pkt - odpowiedź 4 lub 6 (off-by-one error: liczone końce/granice przedziału lub błędna inicjalizacja).
- 0 pkt - inna błędna odpowiedź lub brak.
- UWAGA: Nie przyznaje się 3 pkt i 1 pkt.
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}