# Informatyka — zadanie 1.1

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

- arkusz: Informatyka · Matura · maj 2019 (rozszerzona)
- rok: 2019
- poziom: rozszerzona
- typ: open
- punkty: 5
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 1. Ulubione liczby

Małgosia i Jaś lubią liczby. Małgosia lubi liczby nieparzyste, a Jaś lubi liczby parzyste. Każde z dzieci zapisało po kilka spośród swoich ulubionych liczb na jednej wspólnej kartce. Najpierw Małgosia zapisała wszystkie swoje liczby, a potem Jaś dopisał swoje.

Napisz algorytm (w postaci listy kroków, w pseudokodzie lub w wybranym języku programowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę zapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.

Przy ocenie będzie brana pod uwagę złożoność czasowa Twojego algorytmu. Maksymalną liczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.

**Uwaga:** W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje porównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje.

**Specyfikacja:**
Dane:
- n - liczba całkowita większa od 1
- A[1 n] - tablica zawierająca ciąg n liczb zapisanych przez dzieci (najpierw wszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)

Wynik:
- w - pierwsza od lewej parzysta liczba w tablicy A

**Przykład:**
Dane: n = 10, A[1 n] = {5, 99, 3, 7, 111, 13, 4, 24, 4, 8}
Wynik: w = 4

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

## Poprawna odpowiedź

**Algorytm wyszukiwania binarnego (zmodyfikowanego) - złożoność O(log n):**

p ← 1
k ← n
dopóki p < k wykonuj
s ← (p + k) div 2
jeżeli A[s] mod 2 = 1
p ← s + 1
w przeciwnym przypadku
k ← s
w ← A[p]

## Sposób 1 - wyszukiwanie binarne O(log n) [maksymalna punktacja]

**Kluczowa obserwacja:** ciąg ma strukturę `[nieparzyste, nieparzyste, , parzyste, parzyste, ]`. Szukamy **granicy** między częścią nieparzystą a parzystą - czyli pierwszego indeksu z liczbą parzystą. Tak posortowany ciąg (najpierw 1, potem 0 dla parzystości) idealnie nadaje się do **wyszukiwania binarnego** - szukamy pierwszego wystąpienia 0.

**Idea:** utrzymujemy przedział `[p, k]` zawierający szukaną pierwszą parzystą:
- środek `s = (p+k) div 2`.
- jeśli `A[s]` jest nieparzyste (mod 2 = 1) → granica jest po prawej: `p ← s+1`.
- jeśli `A[s]` jest parzyste → granica może być w `s` lub wcześniej: `k ← s` (NIE `s-1`, bo `s` to kandydat!).
- pętla kończy się gdy `p = k` → `A[p]` to pierwsza parzysta.

**Python:**
```python
def pierwsza_parzysta(A, n):
p, k = 0, n - 1 # indeksowanie od 0 w Python
while p < k:
s = (p + k) // 2
if A[s] % 2 == 1:
p = s + 1
else:
k = s
return A[p]

A = [5, 99, 3, 7, 111, 13, 4, 24, 4, 8]
print(pierwsza_parzysta(A, len(A))) # 4

**Pascal (indeksowanie od 1 jak w CKE):**
```pascal
function PierwszaParzysta(var A: array of LongInt; n: Integer): LongInt;
var p, k, s: Integer;
begin
p := 1; k := n;
while p < k do
begin
s := (p + k) div 2;
if A[s] mod 2 = 1 then
p := s + 1
else
k := s;
end;
PierwszaParzysta := A[p];
end;

**C++:**
```cpp
int pierwszaParzysta(int A[], int n) {
int p = 1, k = n;
while (p < k) {
int s = (p + k) / 2;
if (A[s] % 2 == 1) p = s + 1;
else k = s;
}
return A[p];
}

**Weryfikacja na przykładzie:** A = [5,99,3,7,111,13,4,24,4,8], n=10.
- p=1, k=10 → s=5, A[5]=111 nieparzysta → p=6.
- p=6, k=10 → s=8, A[8]=24 parzysta → k=8.
- p=6, k=8 → s=7, A[7]=4 parzysta → k=7.
- p=6, k=7 → s=6, A[6]=13 nieparzysta → p=7.
- p=7, k=7 → pętla kończy. w = A[7] = 4 ✓

## Sposób 2 - wyszukiwanie liniowe O(n) [max 3 pkt]

Najprostsza wersja - przeglądamy tablicę od lewej, zwracamy pierwszy element parzysty:

dla i od 1 do n wykonuj
jeżeli A[i] mod 2 = 0
w ← A[i]
zakończ

**Python:**
```python
def liniowo(A):
for x in A:
if x % 2 == 0:
return x

Działa poprawnie, ale klucz CKE nagradza maksymalnie 3 pkt zamiast 5 - uczyć się więc rozwiązania binarnego.

## Reference informatyczny - wyszukiwanie binarne

> Reference - Binary Search w wariancie "znajdź pierwsze wystąpienie":
> - Klasyczne wyszukiwanie binarne szuka **dokładnej wartości** - tutaj szukamy **granicy** (pierwszy element spełniający warunek).
> - Niezmiennik pętli: w przedziale `[p, k]` znajduje się szukana wartość.
> - WAŻNE: gdy `A[s]` spełnia warunek (parzyste), ustawiamy `k = s` (NIE `s-1`!), bo `s` może być odpowiedzią.
> - Złożoność: **O(log n)** - w każdej iteracji przedział kurczy się dwukrotnie.
> - Wymagania: monotoniczność warunku (od pewnego momentu wszystkie elementy spełniają warunek).

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.1, max 5 pkt):
> - **5 pkt** - algorytm o złożoności lepszej niż liniowa (binarka):
> - 1 pkt - prawidłowy warunek pętli (`p < k`)
> - 1 pkt - prawidłowe wyznaczenie podziału ciągu (s = (p+k) div 2)
> - 1 pkt - prawidłowe wyznaczenie początku podciągu (p ← s+1)
> - 1 pkt - prawidłowe wyznaczenie końca podciągu (k ← s)
> - 1 pkt - prawidłowe wyznaczenie pierwszego parzystego (w ← A[p])
> - **3 pkt** - algorytm liniowy:
> - 1 pkt - prawidłowy przebieg pętli
> - 1 pkt - sprawdzenie warunku parzystości
> - 1 pkt - wyznaczenie pierwszego parzystego
> - **0 pkt** - błędna lub brak odpowiedzi

## Typowe pułapki

- **`k ← s-1` zamiast `k ← s`** - gubimy kandydata; pętla może minąć poprawny indeks.
- **`p ← s` zamiast `p ← s+1`** - pętla nie kończy się gdy A[s] nieparzysta i p == s.
- **Warunek `p ≤ k`** zamiast `p < k` - niepotrzebna dodatkowa iteracja, ryzyko out-of-bounds.
- **Off-by-one indeksowanie** - CKE używa od 1, Python/C++ od 0.
- **Test parzystości** `A[s] mod 2 = 0` vs `A[s] mod 2 = 1` - łatwo pomylić kierunek.
- **Brak założenia, że co najmniej jedna parzysta liczba istnieje** - algorytm tego nie sprawdza, ale w treści mamy gwarancję (Jaś zapisał co najmniej jedną liczbę).

## Złożoność obliczeniowa

- **Czas: O(log n)** - w każdej iteracji przedział `[p, k]` kurczy się o połowę.
- **Pamięć: O(1)** - kilka zmiennych pomocniczych (p, k, s).
- Dla porównania: rozwiązanie liniowe = O(n) (max 3 pkt w CKE).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2019-05/zad/1.1)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2019-05%2Fzad%2F1.1)

## Podobne zadania

- [Zadanie 1](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/1) — Zadanie 1. Funkcja rekurencyjna Dana jest rekurencyjna funkcja przestaw, której parametrem jest nieujemna liczba całkowita: przestaw(n): r  n mod 100 a  r div
- [Zadanie 2](https://matura.lol/question/informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad/2) — Zadanie 2. (0-6) Całkowity pierwiastek kwadratowy Niech będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym z liczby ݊ nazywamy dodatnią licz
- [Zadanie 5.2](https://matura.lol/question/informatyka-2015-maj-matura-stara-podstawowa-2/zad/5.2) — Zadanie 5.2. (6 pkt) Dla każdego słowa z pliku nowe.txt wypisz to słowo oraz dwie liczby rozdzielone spacją oznaczające: • liczbę wystąpień danego słowa w pliku
- [Zadanie 3](https://matura.lol/question/informatyka-2014-maj-matura-rozszerzona/zad/3) — Zadanie 3. (6 pkt) Przeanalizuj poniższy algorytm dla dodatniej liczby całkowitej n: jeżeli n = 1, to suma ← 1 w przeciwnym przypadku suma ← 1 + n i ← n - 1 dop

_Ostatnia aktualizacja danych: 2026-10-03_