# Informatyka — zadanie 1.2

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

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

## Treść

Zadanie 1.2. (0-4)
Zapisz (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) algorytm
obliczający największe pole powierzchni prostokąta, które nie jest podzielne przez p, a długości
sąsiednich boków tego prostokąta należą do zbioru A i są różne.
Przy ocenie brana będzie pod uwagę złożoność obliczeniowa Twojego algorytmu.
Uwaga:
W zapisie algorytmu możesz wykorzystywać tylko następujące operacje arytmetyczne:
dodawanie, odejmowanie, mnożenie, dzielenie całkowite i obliczanie reszty z dzielenia.
Specyfikacja:
Dane:
n
- liczba całkowita większa od 1
A[1 n] - tablica zawierająca n różnych, dodatnich liczb całkowitych
p
- liczba pierwsza
Wynik:
S
- największe pole powierzchni prostokąta, które nie jest podzielne przez p,
a długości sąsiednich boków tego prostokąta są różne i zawarte w tablicy A;
jeśli nie można zbudować takiego prostokąta, wynikiem powinno być 0 (zero)
MIN_1R
Algorytm
Wypełnia
egzaminator
Nr zadania
1.1.
1.2.
Maks. liczba pkt.
2
4
Uzyskana liczba pkt.
MIN_1R

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

## Poprawna odpowiedź

Algorytm liniowy O(n) - jednokrotne przejście tablicy z aktualizacją dwóch największych elementów niepodzielnych przez p:

max1 ← 0
max2 ← 0
dla i = 1, 2, , n wykonuj:
jeżeli A[i] mod p ≠ 0:
jeżeli A[i] > max1:
max2 ← max1
max1 ← A[i]
w przeciwnym razie jeżeli A[i] > max2:
max2 ← A[i]
S ← max1 * max2

**Wynik:** jeśli max2 = 0 (mniej niż 2 liczby spełniają warunek) → S = 0. W przeciwnym razie S = max1 · max2.

## Sposób 1 - idea algorytmu liniowego

Kluczowa własność (z zad. 1.1): liczba pierwsza p dzieli a·b ⟺ p|a lub p|b. Więc szukamy DWÓCH NAJWIĘKSZYCH RÓŻNYCH elementów A, które **nie są podzielne przez p**.

W jednym przejściu pętli utrzymujemy dwa zmienne:
- `max1` - największa dotąd zaobserwowana liczba niepodzielna przez p,
- `max2` - druga co do wielkości.

Przy nowym elemencie A[i] (jeśli niepodzielny przez p):
- jeśli A[i] > max1 → max2 staje się starym max1, a max1 := A[i],
- inaczej jeśli A[i] > max2 → max2 := A[i].

Gdy max2 = 0, to znaczy że istnieje co najwyżej jedna liczba niepodzielna przez p → S = 0 (max1 * 0 = 0).

## Sposób 2 - implementacja w 3 językach

**Python:**
```python
def max_pole(A, p):
max1, max2 = 0, 0
for x in A:
if x % p != 0:
if x > max1:
max2 = max1
max1 = x
elif x > max2:
max2 = x
return max1 * max2

print(max_pole([7, 5, 11, 33], 3)) # 77
print(max_pole([4, 34, 16, 8, 6, 22, 14, 12, 2, 7], 2)) # 0

**Pascal:**
```pascal
function MaxPole(A: array of LongInt; n, p: LongInt): LongInt;
var i, max1, max2: LongInt;
begin
max1 := 0; max2 := 0;
for i := 0 to n - 1 do
if A[i] mod p <> 0 then
begin
if A[i] > max1 then
begin
max2 := max1;
max1 := A[i];
end
else if A[i] > max2 then
max2 := A[i];
end;
MaxPole := max1 * max2;
end;

**C++:**
```cpp
long long maxPole(int A[], int n, int p) {
long long max1 = 0, max2 = 0;
for (int i = 0; i < n; i++) {
if (A[i] % p != 0) {
if (A[i] > max1) {
max2 = max1;
max1 = A[i];
} else if (A[i] > max2) {
max2 = A[i];
}
}
}
return max1 * max2;
}

## Reference algorytmiczny - wyszukiwanie dwóch największych

> Reference - Dwa największe elementy w tablicy:
> - Algorytm liniowy O(n): jedna pętla, dwie zmienne max1, max2.
> - Aktualizacja: gdy x > max1, przesuń max1→max2, max1=x; w innym razie gdy x > max2, max2=x.
> - Alternatywa: posortuj (O(n log n)) i weź dwa pierwsze - dłużej.
> - W naszym zadaniu dodatkowy filtr `A[i] mod p ≠ 0`.

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.2, max 4 pkt):
> - **4 pkt** - algorytm o złożoności liniowej w pełni poprawny, w tym:
> - 2 pkt - wyznaczenie długości dwóch najdłuższych boków (1 pkt - tylko jednej)
> - 1 pkt - sprawdzanie podzielności przez p (mod p ≠ 0)
> - 1 pkt - uwzględnienie różnych długości boków i przypadku S = 0
> - **2 pkt** - rozwiązanie o złożoności gorszej niż liniowa (np. O(n²) - dwie pętle, lub O(n log n) - sortowanie + wybór)
> - **0 pkt** - błędne lub brak

## Typowe pułapki

- **Pominięcie warunku „boki różne"** - gdy A zawiera duplikaty (treść zadania mówi „różne", więc OK, ale przy implementacji uważać).
- **Pominięcie S = 0 dla niewystarczającej liczby kandydatów** - gdy mniej niż 2 elementy są niepodzielne przez p, max2 pozostaje 0, S = max1·0 = 0 (algorytm sam obsługuje to dzięki inicjalizacji).
- **Nieefektywne rozwiązanie** - sortowanie całej tablicy (O(n log n)) lub porównywanie par (O(n²)) traci punkty za niefektywność. Liniowy algorytm jest WYMAGANY na max ocenę.
- **Wykorzystanie zabronionych operacji** - treść pozwala tylko +, -, *, div, mod. Bez sortowania bibliotecznego (sort()).

## Złożoność obliczeniowa

- **Czas: O(n)** - jedna pętla po n elementach tablicy.
- **Pamięć: O(1)** - tylko stałe zmienne (max1, max2, i).
- **Porównanie:** sortowanie + wybór dwóch pierwszych: O(n log n); brute force par: O(n²). Liniowy jest optymalny.

## Linki

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

## Podobne zadania

- [Zadanie 2.2](https://matura.lol/question/informatyka-2020-kwiecien-probna-rozszerzona/zad/2.2) — Zadanie 2.2. (0-5) W wybranej przez siebie notacji (w postaci pseudokodu, listy kroków, lub języka programowania) napisz algorytm zgodny z poniższą specyfikacją
- [Zadanie 2.2](https://matura.lol/question/informatyka-2026-maj-matura-stara-rozszerzona/zad/2.2) — Zadanie 2.2. (0-4) Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich a i b, o tej samej lic
- [Zadanie 2.2](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/2.2) — Zadanie 2.2. (0-4) Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich a i b, o tej samej lic
- [Zadanie 2.1](https://matura.lol/question/informatyka-2025-czerwiec-matura-rozszerzona/zad/2.1) — Zadanie 2.1. (0-4) Niech k będzie dodatnią liczbą całkowitą, której zapis dziesiętny składa się z parzystej liczby cyfr. Na zapisie dziesiętnym liczby k wykonuj

_Ostatnia aktualizacja danych: 2026-10-03_