# Informatyka — zadanie 4.3

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2015-05/zad/4.3
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2015 (rozszerzona)
- rok: 2015
- poziom: rozszerzona
- typ: open
- punkty: 6
- działy: Programowanie i algorytmika

## Treść

Zadanie 4.3. (0-6)
Znajdź najmniejszą i największą liczbę w pliku liczby.txt. Jako odpowiedź podaj
numery wierszy, w których się one znajdują.
Przykład: Dla zestawu liczb:
101011010011001100111
10001001011101010
1001000
101010011100
1000110
najmniejsza liczba to: 1000110
największa liczba to: 101011010011001100111
Prawidłowa odpowiedź dla powyższego przykładu to: 5, 1.
Do oceny oddajesz:
• plik tekstowy wynik4.txt zawierający odpowiedzi do poszczególnych zadań.
Odpowiedź do każdego zadania powinna być poprzedzona jego numerem.
• plik(i) zawierający(e) komputerową realizację Twoich obliczeń:
Wypełnia
egzaminator
Nr zadania
4.1.
4.2.
4.3.
Maks. liczba pkt.
3
3
6
Uzyskana liczba pkt.
MIN_2R

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

- **Najmniejsza liczba: wiersz 859**
- **Największa liczba: wiersz 925**

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

**Kluczowa obserwacja:** dla porównania liczb binarnych (bez wiodących zer) używamy reguły:
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).

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

**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)

# Sortowanie: najmniejsza = najkrótsza, w razie remisu leksykograficznie
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

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

## Sposób 2 - Python z arbitrary precision int

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

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

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

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

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;
}

**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;

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.

## Reference informatyczny - porównanie liczb i wielkości

> 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).

## Schemat oceniania CKE

> 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.

## Typowe pułapki

- **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.

## Złożoność obliczeniowa

- 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).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2015-05/zad/4.3)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2015-05%2Fzad%2F4.3)

## Podobne zadania

- [Zadanie 2](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/2) — Zadanie 2. Zapis symboliczny W pliku symbole.txt zapisano 2000 napisów. Każdy z nich jest zapisany w osobnym wierszu i składa się z dokładnie 12 znaków spośród:
- [Zadanie 7](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/7) — Zadanie 7. Poszukiwanie wody na Marsie W trzech plikach tekstowych o nazwach laziki.txt, obszary.txt, pomiary.txt zapisano informacje zawierające dane o poszuki
- [Zadanie 3](https://matura.lol/question/informatyka-2023-maj-matura-rozszerzona/zad/3) — Zadanie 3. Liczba Pi Pewien matematyk jest zafascynowany liczbą π ≈ 3,14159265 do tego stopnia, że zapisał jej rozwinięcie dziesiętne z dokładnością do 10 000 c
- [Zadanie 3](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/3) — Zadanie 3. Dron Tor lotu pewnego drona składa się z prostych odcinków. Lot rozpoczyna się w punkcie (0, 0), a kończy w punkcie (20000, 0). Dron poza startem i l

_Ostatnia aktualizacja danych: 2026-10-03_