{"id":"informatyka-2017-maj-matura-rozszerzona/zad/6.2","paper_id":"informatyka-2017-maj-matura-rozszerzona","number":"6.2","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2017,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 6.1.\n\nPodaj, ile wynosi najmniejsza liczba wierszy, które należy usunąć, żeby obraz miał pionową oś symetrii. Obraz ma pionową oś symetrii, jeśli w każdym wierszu i-ty piksel od lewej strony przyjmuje tę samą wartość, co i-ty piksel od prawej strony, dla dowolnego 1 ≤ i ≤ 320.\n\nDla danych z pliku przyklad.txt wynikiem jest 3.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Najmniejsza liczba wierszy do usunięcia: 149** (z 200 wierszy w `dane.txt`).\n\nDla `przyklad.txt`: 3.\n\nInterpretacja: obraz będzie miał pionową oś symetrii, jeśli zostawimy tylko te wiersze, które SAMODZIELNIE są palindromami (czytane od lewej = od prawej). Wystarczy zliczyć wiersze NIE-palindromowe - te trzeba usunąć.\n\nPionowa oś symetrii działa NIEZALEŻNIE w każdym wierszu - wiersz jest \"symetryczny\", gdy A[k] = A[321-k] dla k = 1 160 (lub równoważnie [0 159] przy indeksowaniu od 0).\n\n## Sposób 1 - Python (najczystszy)\n\n```python\nusuwajacych = 0\nwith open('dane.txt') as f:\nfor linia in f:\nwiersz = linia.split() # 320 stringow\n# Sprawdz palindrom\nif wiersz != wiersz[::-1]:\nusuwajacych += 1\n\nprint(usuwajacych) # 149\n\nLub jedno-linijkowo:\n```python\nwith open('dane.txt') as f:\nprint(sum(1 for l in f if (w := l.split()) != w[::-1]))\n\n## Sposób 2 - C++\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nint main() {\nifstream plik(\"dane.txt\");\nint do_usuniecia = 0;\nstring linia;\nwhile (getline(plik, linia)) {\nvector w;\nsize_t pos = 0, next;\n// Parsuj liczby z linii\nwhile ((next = linia.find(' ', pos)) != string::npos) {\nw.push_back(stoi(linia.substr(pos, next - pos)));\npos = next + 1;\n}\nif (pos < linia.size()) w.push_back(stoi(linia.substr(pos)));\n// Sprawdz palindrom\nbool palindrom = true;\nint n = w.size();\nfor (int i = 0; i < n / 2; i++) {\nif (w[i] != w[n - 1 - i]) { palindrom = false; break; }\n}\nif (!palindrom) do_usuniecia++;\n}\ncout << do_usuniecia << endl; // 149\nreturn 0;\n}\n\n## Sposób 3 - Pascal\n\n```pascal\nprogram OsSymetrii;\nvar\nf: TextFile;\nwiersz: array[1 320] of Integer;\ni, j, n: Integer;\ndo_usuniecia: Integer;\npalindrom: Boolean;\nbegin\nAssignFile(f, 'dane.txt');\nReset(f);\ndo_usuniecia := 0;\nfor i := 1 to 200 do\nbegin\nfor j := 1 to 320 do Read(f, wiersz[j]);\nReadln(f);\npalindrom := True;\nfor j := 1 to 160 do\nif wiersz[j] <> wiersz[321 - j] then\nbegin\npalindrom := False;\nBreak;\nend;\nif not palindrom then Inc(do_usuniecia);\nend;\nCloseFile(f);\nWriteln(do_usuniecia); // 149\nend.\n\n## Reference algorytmiczny - sprawdzanie palindromu\n\n> Reference - palindromiczność wiersza:\n> - Wiersz jest palindromem ⇔ wiersz[i] = wiersz[n-1-i] dla każdego i ∈ [0, n/2).\n> - Złożoność: O(n/2) = O(n) na wiersz.\n> - W Pythonie najprościej: `wiersz == wiersz[::-1]` (operator slice odwracający listę).\n> - Dla 200 wierszy × 320 pikseli: łącznie 200 × 160 = 32 000 porównań. Szybko.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 6.2, max 2 pkt):\n> - **2 pkt** - prawidłowa odpowiedź: **149**.\n> - **0 pkt** - odpowiedź błędna lub brak.\n> - **UWAGA:** Nie przyznaje się 1 pkt.\n\n## Typowe pułapki\n\n- **Mylenie sensu pionowej osi symetrii** - to symetria LEWO-PRAWO (kolumna i = kolumna 321-i), a nie góra-dół.\n- **\"Najmniejsza liczba wierszy do usunięcia\"** - to po prostu liczba wierszy NIE-palindromowych (każdy taki MUSI być usunięty, palindromowe MOGĄ zostać).\n- **Indeksowanie 1 320 vs 0 319** - w Python od 0, w pseudokodzie CKE od 1. `wiersz[i] vs wiersz[321-i]` jeśli indeksujemy od 1, a `wiersz[i] vs wiersz[319-i]` od 0.\n- **Tylko połowa porównań wystarczy** - sprawdzaj `i` od 0 do n/2-1 (lub do n//2). Sprawdzanie wszystkich par jest podwójną pracą.\n- **Pomylenie z liczbą wierszy POZOSTAŁYCH** - pytanie o USUNIĘTE (149), nie zachowane (51 = 200 - 149).\n\n## Złożoność obliczeniowa\n\n- Wczytanie: O(n × m) = O(64 000).\n- Sprawdzenie palindromu per wiersz: O(m/2) = O(160) = O(m).\n- **Całkowita: O(n × m) = O(64 000)**, liniowa względem rozmiaru obrazu.","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, ile wynosi najmniejsza liczba wierszy, które należy usunąć, żeby obraz miał pionową oś symetrii. Obraz ma pionową oś symetrii, jeśli w każdym wierszu i-ty piksel od lewej strony przyjmuje tę samą wartość, co i-ty piksel od prawej strony, dla dowolnego 1 ≤ i ≤ 320.

\n

Dla danych z pliku przyklad.txt wynikiem jest 3.

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

Poprawna odpowiedź

\n

Najmniejsza liczba wierszy do usunięcia: 149 (z 200 wierszy w dane.txt).

\n

Dla przyklad.txt: 3.

\n

Interpretacja: obraz będzie miał pionową oś symetrii, jeśli zostawimy tylko te wiersze, które SAMODZIELNIE są palindromami (czytane od lewej = od prawej). Wystarczy zliczyć wiersze NIE-palindromowe - te trzeba usunąć.

\n

Pionowa oś symetrii działa NIEZALEŻNIE w każdym wierszu - wiersz jest "symetryczny", gdy A[k] = A[321-k] dla k = 1 160 (lub równoważnie [0 159] przy indeksowaniu od 0).

\n

Sposób 1 - Python (najczystszy)

\n

```python
usuwajacych = 0
with open('dane.txt') as f:
for linia in f:
wiersz = linia.split() # 320 stringow

\n

Sprawdz palindrom

\n

if wiersz != wiersz[::-1]:
usuwajacych += 1

\n

print(usuwajacych) # 149

\n

Lub jedno-linijkowo:
```python
with open('dane.txt') as f:
print(sum(1 for l in f if (w := l.split()) != w[::-1]))

\n

Sposób 2 - C++

\n

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

\n

int main() {
ifstream plik("dane.txt");
int do_usuniecia = 0;
string linia;
while (getline(plik, linia)) {
vector<int> w;
size_t pos = 0, next;
// Parsuj liczby z linii
while ((next = linia.find(' ', pos)) != string::npos) {
w.push_back(stoi(linia.substr(pos, next - pos)));
pos = next + 1;
}
if (pos < linia.size()) w.push_back(stoi(linia.substr(pos)));
// Sprawdz palindrom
bool palindrom = true;
int n = w.size();
for (int i = 0; i < n / 2; i++) {
if (w[i] != w[n - 1 - i]) { palindrom = false; break; }
}
if (!palindrom) do_usuniecia++;
}
cout << do_usuniecia << endl; // 149
return 0;
}

\n

Sposób 3 - Pascal

\n

```pascal
program OsSymetrii;
var
f: TextFile;
wiersz: array[1 320] of Integer;
i, j, n: Integer;
do_usuniecia: Integer;
palindrom: Boolean;
begin
AssignFile(f, 'dane.txt');
Reset(f);
do_usuniecia := 0;
for i := 1 to 200 do
begin
for j := 1 to 320 do Read(f, wiersz[j]);
Readln(f);
palindrom := True;
for j := 1 to 160 do
if wiersz[j] <> wiersz[321 - j] then
begin
palindrom := False;
Break;
end;
if not palindrom then Inc(do_usuniecia);
end;
CloseFile(f);
Writeln(do_usuniecia); // 149
end.

\n

Reference algorytmiczny - sprawdzanie palindromu

\n
Reference - palindromiczność wiersza:
- Wiersz jest palindromem ⇔ wiersz[i] = wiersz[n-1-i] dla każdego i ∈ [0, n/2).
- Złożoność: O(n/2) = O(n) na wiersz.
- W Pythonie najprościej: wiersz == wiersz[::-1] (operator slice odwracający listę).
- Dla 200 wierszy × 320 pikseli: łącznie 200 × 160 = 32 000 porównań. Szybko.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 6.2, max 2 pkt):
- 2 pkt - prawidłowa odpowiedź: 149.
- 0 pkt - odpowiedź błędna lub brak.
- UWAGA: Nie przyznaje się 1 pkt.
\n

Typowe pułapki

\n
  • Mylenie sensu pionowej osi symetrii - to symetria LEWO-PRAWO (kolumna i = kolumna 321-i), a nie góra-dół.
  • "Najmniejsza liczba wierszy do usunięcia" - to po prostu liczba wierszy NIE-palindromowych (każdy taki MUSI być usunięty, palindromowe MOGĄ zostać).
  • Indeksowanie 1 320 vs 0 319 - w Python od 0, w pseudokodzie CKE od 1. wiersz[i] vs wiersz[321-i] jeśli indeksujemy od 1, a wiersz[i] vs wiersz[319-i] od 0.
  • Tylko połowa porównań wystarczy - sprawdzaj i od 0 do n/2-1 (lub do n//2). Sprawdzanie wszystkich par jest podwójną pracą.
  • Pomylenie z liczbą wierszy POZOSTAŁYCH - pytanie o USUNIĘTE (149), nie zachowane (51 = 200 - 149).
\n

Złożoność obliczeniowa

\n
  • Wczytanie: O(n × m) = O(64 000).
  • Sprawdzenie palindromu per wiersz: O(m/2) = O(160) = O(m).
  • Całkowita: O(n × m) = O(64 000), liniowa względem rozmiaru obrazu.
"}]}