{"id":"informatyka-2015-maj-matura-rozszerzona/zad/4.3","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"4.3","points":6,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 4.1.\n\nZnajdź najmniejszą i największą liczbę w pliku liczby.txt. Jako odpowiedź podaj numery wierszy, w których się one znajdują.\n\nPrzykład: dla zestawu 101011010011001100111, 10001001011101010, 1001000, 101010011100, 1000110 - odpowiedź to 5, 1 (wiersz 5 = najmniejsza, wiersz 1 = największa).","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n- **Najmniejsza liczba: wiersz 859**\n- **Największa liczba: wiersz 925**\n\n## Sposób 1 - porównywanie liczb binarnych jako stringów\n\n**Kluczowa obserwacja:** dla porównania liczb binarnych (bez wiodących zer) używamy reguły:\n1. **Dłuższy string = większa liczba** (bo 100000 > 11111 mimo że 11111 ma wyższe cyfry).\n2. **Przy równej długości** - porównanie leksykograficzne odpowiada numerycznemu (bo '0' < '1' i pozycje są takie same).\n\nDlatego porównujemy: `(len(s), s)` - tuple porównuje element po elemencie.\n\n**Python:**\n```python\nz_wierszem = []\nwith open('liczby.txt') as f:\nfor i, linia in enumerate(f, start=1):\ns = linia.strip()\nz_wierszem.append((len(s), s, i)) # (długość, string, nr wiersza)\n\n# Sortowanie: najmniejsza = najkrótsza, w razie remisu leksykograficznie\nz_wierszem.sort() # rosnąco\nnajmniejsza = z_wierszem[0]\nnajwieksza = z_wierszem[-1]\nprint('najmniejsza: wiersz', najmniejsza[2]) # 859\nprint('największa: wiersz', najwieksza[2]) # 925\n\nLub bez sortowania (1 przejście):\n```python\nmin_dl, min_s, min_w = None, None, None\nmax_dl, max_s, max_w = None, None, None\nwith open('liczby.txt') as f:\nfor i, linia in enumerate(f, start=1):\ns = linia.strip()\nklucz = (len(s), s)\nif min_dl is None or klucz < (min_dl, min_s):\nmin_dl, min_s, min_w = len(s), s, i\nif max_dl is None or klucz > (max_dl, max_s):\nmax_dl, max_s, max_w = len(s), s, i\nprint('min wiersz:', min_w) # 859\nprint('max wiersz:', max_w) # 925\n\n## Sposób 2 - Python z arbitrary precision int\n\nPython obsługuje liczby całkowite o dowolnej precyzji, więc można:\n```python\nliczby = []\nwith open('liczby.txt') as f:\nfor i, linia in enumerate(f, start=1):\nn = int(linia.strip(), 2) # konwersja binarna → dec\nliczby.append((n, i))\nliczby.sort()\nprint('min:', liczby[0][1]) # 859\nprint('max:', liczby[-1][1]) # 925\n\n**Uwaga:** w C++/Pascal nie ma arbitrary precision dla integerów - musimy używać porównania stringowego.\n\n**C++:**\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nbool mniejsza(const string& a, const string& b) {\nif (a.length() != b.length()) return a.length() < b.length();\nreturn a < b; // leksykograficzne porównanie\n}\n\nint main() {\nifstream plik(\"liczby.txt\");\nstring s, minS, maxS;\nint i = 0, minW = 0, maxW = 0;\nwhile (plik >> s) {\ni++;\nif (minW == 0 || mniejsza(s, minS)) { minS = s; minW = i; }\nif (maxW == 0 || mniejsza(maxS, s)) { maxS = s; maxW = i; }\n}\ncout << \"min wiersz: \" << minW << endl; // 859\ncout << \"max wiersz: \" << maxW << endl; // 925\nreturn 0;\n}\n\n**Pascal:**\n```pascal\nfunction Mniejsza(a, b: String): Boolean;\nbegin\nif Length(a) <> Length(b) then\nMniejsza := Length(a) < Length(b)\nelse\nMniejsza := a < b;\nend;\n\nvar\nf: TextFile;\ns, minS, maxS: String;\ni, minW, maxW: Integer;\nbegin\nAssignFile(f, 'liczby.txt');\nReset(f);\ni := 0; minW := 0; maxW := 0;\nwhile not Eof(f) do\nbegin\nReadln(f, s);\nInc(i);\nif (minW = 0) or Mniejsza(s, minS) then begin minS := s; minW := i; end;\nif (maxW = 0) or Mniejsza(maxS, s) then begin maxS := s; maxW := i; end;\nend;\nCloseFile(f);\nWriteln('min wiersz: ', minW); // 859\nWriteln('max wiersz: ', maxW); // 925\nend.\n\n## Reference informatyczny - porównanie liczb i wielkości\n\n> Reference - Big number comparison:\n> - Liczby binarne BEZ wiodących zer: dłuższa = większa. Przy równej długości - leksykograficzne porównanie odpowiada numerycznemu.\n> - **Python**: `int(s, 2)` konwertuje string binarny na int (arbitrary precision).\n> - **C++/Pascal**: dla liczb > 63 bity konieczne porównanie stringowe lub biblioteka BigNum.\n> - **One-pass minmax**: jedno przejście, dwa porównania → O(n). Lepsze niż sortowanie O(n log n).\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.3, max 6 pkt):\n> - **6 pkt** - poprawne min wiersz 859 ORAZ max wiersz 925\n> - **4 pkt** - tylko 250 wierszy uwzględnione (wynik: 125 min, 107 max)\n> - **3 pkt** - poprawnie tylko jeden z dwóch wierszy (859 ALBO 925)\n> - **2 pkt** - tylko 250 wierszy ORAZ tylko jeden poprawny\n> - **0 pkt** - niepełna lub błędna albo brak\n> - Nie przyznaje się 5 pkt ani 1 pkt.\n\n## Typowe pułapki\n\n- **Porównanie leksykograficzne bez uwzględnienia długości**: \"110\" < \"22\" w sensie znaków, ale jako liczby 110 > 22. Dla liczb binarnych: \"110\" (=6) vs \"100\" (=4) - leksykograficzne `\"110\" > \"100\"` ✓ ZGADZA SIĘ. Problem dopiero przy różnej długości: \"11\" (=3) vs \"100\" (=4) - leksykograficzne `\"11\" > \"100\"` ❌ ALE numerycznie \"11\" < \"100\". Dlatego SPRAWDZAĆ DŁUGOŚĆ NAJPIERW.\n- **Próba konwersji na int w C++/Pascal** - przepełnienie dla 250-bitowych liczb.\n- **Off-by-one w numeracji wierszy** - zacząć od 1, nie 0.\n- **Limit 250 wierszy** - Pascal w starych wersjach.\n- **Pomylenie min z max** - łatwo zamienić warunki.\n\n## Złożoność obliczeniowa\n\n- One-pass minmax: **O(N · L)**, gdzie N = 1000, L = 250 (porównanie stringów).\n- Sortowanie: O(N log N · L) = wolniejsze, niepotrzebne.\n- Pamięć: O(L) (tylko 2 stringi: min i max).","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 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 4.1.

\n

Znajdź najmniejszą i największą liczbę w pliku liczby.txt. Jako odpowiedź podaj numery wierszy, w których się one znajdują.

\n

Przykład: dla zestawu 101011010011001100111, 10001001011101010, 1001000, 101010011100, 1000110 - odpowiedź to 5, 1 (wiersz 5 = najmniejsza, wiersz 1 = największa).

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

Poprawna odpowiedź

\n
  • Najmniejsza liczba: wiersz 859
  • Największa liczba: wiersz 925
\n

Sposób 1 - porównywanie liczb binarnych jako stringów

\n

Kluczowa obserwacja: dla porównania liczb binarnych (bez wiodących zer) używamy reguły:

\n
  1. Dłuższy string = większa liczba (bo 100000 > 11111 mimo że 11111 ma wyższe cyfry).
  2. Przy równej długości - porównanie leksykograficzne odpowiada numerycznemu (bo '0' < '1' i pozycje są takie same).
\n

Dlatego porównujemy: (len(s), s) - tuple porównuje element po elemencie.

\n

Python:
```python
z_wierszem = []
with open('liczby.txt') as f:
for i, linia in enumerate(f, start=1):
s = linia.strip()
z_wierszem.append((len(s), s, i)) # (długość, string, nr wiersza)

\n

Sortowanie: najmniejsza = najkrótsza, w razie remisu leksykograficznie

\n

z_wierszem.sort() # rosnąco
najmniejsza = z_wierszem[0]
najwieksza = z_wierszem[-1]
print('najmniejsza: wiersz', najmniejsza[2]) # 859
print('największa: wiersz', najwieksza[2]) # 925

\n

Lub bez sortowania (1 przejście):
```python
min_dl, min_s, min_w = None, None, None
max_dl, max_s, max_w = None, None, None
with open('liczby.txt') as f:
for i, linia in enumerate(f, start=1):
s = linia.strip()
klucz = (len(s), s)
if min_dl is None or klucz < (min_dl, min_s):
min_dl, min_s, min_w = len(s), s, i
if max_dl is None or klucz > (max_dl, max_s):
max_dl, max_s, max_w = len(s), s, i
print('min wiersz:', min_w) # 859
print('max wiersz:', max_w) # 925

\n

Sposób 2 - Python z arbitrary precision int

\n

Python obsługuje liczby całkowite o dowolnej precyzji, więc można:
```python
liczby = []
with open('liczby.txt') as f:
for i, linia in enumerate(f, start=1):
n = int(linia.strip(), 2) # konwersja binarna → dec
liczby.append((n, i))
liczby.sort()
print('min:', liczby[0][1]) # 859
print('max:', liczby[-1][1]) # 925

\n

Uwaga: w C++/Pascal nie ma arbitrary precision dla integerów - musimy używać porównania stringowego.

\n

C++:
```cpp
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

\n

bool mniejsza(const string& a, const string& b) {
if (a.length() != b.length()) return a.length() < b.length();
return a < b; // leksykograficzne porównanie
}

\n

int main() {
ifstream plik("liczby.txt");
string s, minS, maxS;
int i = 0, minW = 0, maxW = 0;
while (plik >> s) {
i++;
if (minW == 0 || mniejsza(s, minS)) { minS = s; minW = i; }
if (maxW == 0 || mniejsza(maxS, s)) { maxS = s; maxW = i; }
}
cout << "min wiersz: " << minW << endl; // 859
cout << "max wiersz: " << maxW << endl; // 925
return 0;
}

\n

Pascal:
```pascal
function Mniejsza(a, b: String): Boolean;
begin
if Length(a) <> Length(b) then
Mniejsza := Length(a) < Length(b)
else
Mniejsza := a < b;
end;

\n

var
f: TextFile;
s, minS, maxS: String;
i, minW, maxW: Integer;
begin
AssignFile(f, 'liczby.txt');
Reset(f);
i := 0; minW := 0; maxW := 0;
while not Eof(f) do
begin
Readln(f, s);
Inc(i);
if (minW = 0) or Mniejsza(s, minS) then begin minS := s; minW := i; end;
if (maxW = 0) or Mniejsza(maxS, s) then begin maxS := s; maxW := i; end;
end;
CloseFile(f);
Writeln('min wiersz: ', minW); // 859
Writeln('max wiersz: ', maxW); // 925
end.

\n

Reference informatyczny - porównanie liczb i wielkości

\n
Reference - Big number comparison:
- Liczby binarne BEZ wiodących zer: dłuższa = większa. Przy równej długości - leksykograficzne porównanie odpowiada numerycznemu.
- Python: int(s, 2) konwertuje string binarny na int (arbitrary precision).
- C++/Pascal: dla liczb > 63 bity konieczne porównanie stringowe lub biblioteka BigNum.
- One-pass minmax: jedno przejście, dwa porównania → O(n). Lepsze niż sortowanie O(n log n).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.3, max 6 pkt):
- 6 pkt - poprawne min wiersz 859 ORAZ max wiersz 925
- 4 pkt - tylko 250 wierszy uwzględnione (wynik: 125 min, 107 max)
- 3 pkt - poprawnie tylko jeden z dwóch wierszy (859 ALBO 925)
- 2 pkt - tylko 250 wierszy ORAZ tylko jeden poprawny
- 0 pkt - niepełna lub błędna albo brak
- Nie przyznaje się 5 pkt ani 1 pkt.
\n

Typowe pułapki

\n
  • Porównanie leksykograficzne bez uwzględnienia długości: "110" < "22" w sensie znaków, ale jako liczby 110 > 22. Dla liczb binarnych: "110" (=6) vs "100" (=4) - leksykograficzne "110" > "100" ✓ ZGADZA SIĘ. Problem dopiero przy różnej długości: "11" (=3) vs "100" (=4) - leksykograficzne "11" > "100" ❌ ALE numerycznie "11" < "100". Dlatego SPRAWDZAĆ DŁUGOŚĆ NAJPIERW.
  • Próba konwersji na int w C++/Pascal - przepełnienie dla 250-bitowych liczb.
  • Off-by-one w numeracji wierszy - zacząć od 1, nie 0.
  • Limit 250 wierszy - Pascal w starych wersjach.
  • Pomylenie min z max - łatwo zamienić warunki.
\n

Złożoność obliczeniowa

\n
  • One-pass minmax: O(N · L), gdzie N = 1000, L = 250 (porównanie stringów).
  • Sortowanie: O(N log N · L) = wolniejsze, niepotrzebne.
  • Pamięć: O(L) (tylko 2 stringi: min i max).
"}]}