{"id":"informatyka-2015-maj-matura-rozszerzona/zad/4.1","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"4.1","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 4. Liczby binarne\n\nW pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie. Każda liczba zapisana jest w osobnym wierszu. Każda liczba binarna zawiera co najwyżej 250 cyfr binarnych, co oznacza, że w wielu językach programowania wartości niektórych z tych liczb nie da się zapamiętać w pojedynczej zmiennej typu całkowitoliczbowego.\n\nPrzykład: Dla zestawu liczb 101011010011001100111, 10001001, 1000000, 101010011100, 100010 - wynikiem jest 3 (3 liczby mają w zapisie więcej zer niż jedynek).\n\nPodaj, ile liczb z pliku liczby.txt ma w swoim zapisie binarnym więcej zer niż jedynek.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**422** liczb z pliku liczby.txt ma więcej zer niż jedynek w zapisie binarnym.\n\n## Sposób 1 - przetwarzanie ciągu znaków (każda liczba to STRING, nie int)\n\nKluczowa obserwacja: liczby mają do 250 cyfr binarnych → nie mieszczą się w int64 (max ~63 bity). Dlatego traktujemy każdą liczbę jako **string** i zliczamy znaki.\n\n**Python:**\n```python\nlicznik = 0\nwith open('liczby.txt') as f:\nfor linia in f:\ns = linia.strip() # usuwa whitespace, \\n\nzera = s.count('0')\njedynki = s.count('1')\nif zera > jedynki:\nlicznik += 1\nprint(licznik) # 422\n\n## Sposób 2 - implementacja w C++ i Pascal\n\n**C++:**\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nint main() {\nifstream plik(\"liczby.txt\");\nstring linia;\nint licznik = 0;\nwhile (plik >> linia) {\nint zera = 0, jedynki = 0;\nfor (char c : linia) {\nif (c == '0') zera++;\nelse if (c == '1') jedynki++;\n}\nif (zera > jedynki) licznik++;\n}\ncout << licznik << endl; // 422\nreturn 0;\n}\n\n**Pascal:**\n```pascal\nprogram LiczbyBinarne;\nvar\nf: TextFile;\ns: String;\ni, zera, jedynki, licznik: Integer;\nbegin\nAssignFile(f, 'liczby.txt');\nReset(f);\nlicznik := 0;\nwhile not Eof(f) do\nbegin\nReadln(f, s);\nzera := 0; jedynki := 0;\nfor i := 1 to Length(s) do\nif s[i] = '0' then Inc(zera)\nelse if s[i] = '1' then Inc(jedynki);\nif zera > jedynki then Inc(licznik);\nend;\nCloseFile(f);\nWriteln(licznik); // 422\nend.\n\n## Reference informatyczny - operacje na napisach\n\n> Reference - String processing:\n> - **Python**: `s.count('0')` - liczba wystąpień znaku '0'. O(n).\n> - **C++**: `std::count(s.begin(), s.end(), '0')` z ``. Lub pętla for.\n> - **Pascal**: pętla for i := 1 to Length(s).\n> - **Plik tekstowy**: czytanie linijka po linijce - `for line in f` (Python), `getline()` (C++), `Readln` (Pascal).\n> - Kluczowe: liczby binarne mogą być długie (250 cyfr = ~10^75) - NIE używaj typu int!\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.1, max 3 pkt):\n> - **3 pkt** - poprawna odpowiedź **422**\n> - **2 pkt** - uwzględnienie tylko 250 wierszy (wynik: 98) - częsty błąd Pascala przy odczycie ograniczonym\n> - **1 pkt** - nieuwzględnienie ostatniego znaku w wierszu (wynik: 419) - np. zatrzymanie pętli na n-1\n> - **0 pkt** - odpowiedź niepełna lub błędna albo brak\n\n## Typowe pułapki\n\n- **Konwersja na int**: `int('1010 250bitów', 2)` w Pythonie zadziała (Python ma arbitrary precision), ale w C++/Pascal `long long` to maksimum 63 bity - przepełnienie. Lepiej trzymać jako string.\n- **Pomylenie liczby zer z jedynkami** - sprawdź `zera > jedynki`, nie `zera >= jedynki`.\n- **Zliczanie ostatniego znaku** - w Pascal `Length(s)` zwraca długość włącznie z ostatnim znakiem.\n- **Pomylenie czytania**: w Pascal `Readln(f, s)` wczytuje całą linię razem z `\\n`. Sprawdź czy nie ma whitespace na końcu.\n- **Limit 250 wierszy zamiast 1000** - Pascal ma czasem domyślny limit linii w starych wersjach.\n\n## Złożoność obliczeniowa\n\n- Przetwarzanie pliku: O(N · L), gdzie N = 1000 (liczb), L = 250 (max długość). To O(250 000) = bardzo szybko.\n- Pamięć: O(L) (jedna linia w pamięci na raz).\n- **Całkowita: O(N · L)**.","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":"

Zadanie 4. Liczby binarne

\n

W pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie. Każda liczba zapisana jest w osobnym wierszu. Każda liczba binarna zawiera co najwyżej 250 cyfr binarnych, co oznacza, że w wielu językach programowania wartości niektórych z tych liczb nie da się zapamiętać w pojedynczej zmiennej typu całkowitoliczbowego.

\n

Przykład: Dla zestawu liczb 101011010011001100111, 10001001, 1000000, 101010011100, 100010 - wynikiem jest 3 (3 liczby mają w zapisie więcej zer niż jedynek).

\n

Podaj, ile liczb z pliku liczby.txt ma w swoim zapisie binarnym więcej zer niż jedynek.

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

Poprawna odpowiedź

\n

422 liczb z pliku liczby.txt ma więcej zer niż jedynek w zapisie binarnym.

\n

Sposób 1 - przetwarzanie ciągu znaków (każda liczba to STRING, nie int)

\n

Kluczowa obserwacja: liczby mają do 250 cyfr binarnych → nie mieszczą się w int64 (max ~63 bity). Dlatego traktujemy każdą liczbę jako string i zliczamy znaki.

\n

Python:
```python
licznik = 0
with open('liczby.txt') as f:
for linia in f:
s = linia.strip() # usuwa whitespace, \\n
zera = s.count('0')
jedynki = s.count('1')
if zera > jedynki:
licznik += 1
print(licznik) # 422

\n

Sposób 2 - implementacja w C++ i Pascal

\n

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

\n

int main() {
ifstream plik("liczby.txt");
string linia;
int licznik = 0;
while (plik >> linia) {
int zera = 0, jedynki = 0;
for (char c : linia) {
if (c == '0') zera++;
else if (c == '1') jedynki++;
}
if (zera > jedynki) licznik++;
}
cout << licznik << endl; // 422
return 0;
}

\n

Pascal:
```pascal
program LiczbyBinarne;
var
f: TextFile;
s: String;
i, zera, jedynki, licznik: Integer;
begin
AssignFile(f, 'liczby.txt');
Reset(f);
licznik := 0;
while not Eof(f) do
begin
Readln(f, s);
zera := 0; jedynki := 0;
for i := 1 to Length(s) do
if s[i] = '0' then Inc(zera)
else if s[i] = '1' then Inc(jedynki);
if zera > jedynki then Inc(licznik);
end;
CloseFile(f);
Writeln(licznik); // 422
end.

\n

Reference informatyczny - operacje na napisach

\n
Reference - String processing:
- Python: s.count('0') - liczba wystąpień znaku '0'. O(n).
- C++: std::count(s.begin(), s.end(), '0') z <algorithm>. Lub pętla for.
- Pascal: pętla for i := 1 to Length(s).
- Plik tekstowy: czytanie linijka po linijce - for line in f (Python), getline() (C++), Readln (Pascal).
- Kluczowe: liczby binarne mogą być długie (250 cyfr = ~10^75) - NIE używaj typu int!
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.1, max 3 pkt):
- 3 pkt - poprawna odpowiedź 422
- 2 pkt - uwzględnienie tylko 250 wierszy (wynik: 98) - częsty błąd Pascala przy odczycie ograniczonym
- 1 pkt - nieuwzględnienie ostatniego znaku w wierszu (wynik: 419) - np. zatrzymanie pętli na n-1
- 0 pkt - odpowiedź niepełna lub błędna albo brak
\n

Typowe pułapki

\n
  • Konwersja na int: int('1010 250bitów', 2) w Pythonie zadziała (Python ma arbitrary precision), ale w C++/Pascal long long to maksimum 63 bity - przepełnienie. Lepiej trzymać jako string.
  • Pomylenie liczby zer z jedynkami - sprawdź zera > jedynki, nie zera >= jedynki.
  • Zliczanie ostatniego znaku - w Pascal Length(s) zwraca długość włącznie z ostatnim znakiem.
  • Pomylenie czytania: w Pascal Readln(f, s) wczytuje całą linię razem z \\n. Sprawdź czy nie ma whitespace na końcu.
  • Limit 250 wierszy zamiast 1000 - Pascal ma czasem domyślny limit linii w starych wersjach.
\n

Złożoność obliczeniowa

\n
  • Przetwarzanie pliku: O(N · L), gdzie N = 1000 (liczb), L = 250 (max długość). To O(250 000) = bardzo szybko.
  • Pamięć: O(L) (jedna linia w pamięci na raz).
  • Całkowita: O(N · L).
"}]}