# Informatyka — zadanie 2.1

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

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

## Treść

Zadanie 2. Krajobraz

W pewnym paśmie górskim znajduje się n szczytów, które będziemy przedstawiać jako punkty w układzie kartezjańskim na płaszczyźnie. Wszystkie punkty leżą powyżej osi OX, tzn. druga współrzędna (y) każdego punktu jest dodatnia.

W punkcie (0,0) stoi obserwator. Jeśli dwa szczyty A i B mają współrzędne (xA, yA) oraz (xB, yB), to mówimy, że:
- szczyt A jest dla obserwatora widoczny na lewo od B, jeśli xA/yA < xB/yB;
- szczyt B jest widoczny na lewo od A, jeśli xA/yA > xB/yB.

Wiemy, że żadne dwa szczyty nie leżą w jednej linii z obserwatorem, a zatem dla obserwatora te szczyty nie zasłaniają się nawzajem.

Przykład (4 szczyty): D(-2,2), A(1,3), B(3,4), C(2,1). Obserwator widzi kolejno: D, A, B, C.

Współrzędne szczytów dane są w dwóch tablicach X[1 n] oraz Y[1 n] - szczyt numer i ma współrzędne (X[i], Y[i]).

**Specyfikacja:**
Dane:
- n - liczba całkowita dodatnia
- X[1 n] - tablica liczb całkowitych
- Y[1 n] - tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n. Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.

Wynik:
- x, y - współrzędne skrajnie lewego szczytu spośród tych opisanych w tablicach X i Y.

Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda współrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich pozostałych szczytów.

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

## Poprawna odpowiedź

**Algorytm (pseudokod):**

k ← 1
dla i = 2, 3, , n wykonuj:
jeżeli X[i]/Y[i] < X[k]/Y[k]:
k ← i
x ← X[k]
y ← Y[k]

Lub równoważnie (bez dzielenia, uważając na znak Y[i] > 0):
k ← 1
dla i = 2, 3, , n wykonuj:
jeżeli X[i] * Y[k] < X[k] * Y[i]:
k ← i
x ← X[k]
y ← Y[k]

## Sposób 1 - analiza problemu i klasyczny algorytm znajdowania minimum

**Idea:** szczyt jest "widoczny na lewo" gdy ma najmniejszą wartość ilorazu `X[i]/Y[i]`. Szukamy więc **MINIMUM** spośród wszystkich ilorazów `X[i]/Y[i]`.

Algorytm to standardowe **wyszukiwanie minimum** w tablicy z modyfikacją w warunku porównania:
1. Załóżmy, że minimum jest na pozycji 1 (k = 1).
2. Iterujemy i od 2 do n.
3. Jeśli iloraz pozycji i jest mniejszy niż na pozycji k → aktualizujemy k = i.
4. Po pętli zwracamy współrzędne (X[k], Y[k]).

## Sposób 2 - implementacja Python

```python
def skrajnie_lewy(X, Y):
n = len(X)
k = 0 # indeks od 0 w Python
for i in range(1, n):
if X[i] / Y[i] < X[k] / Y[k]:
k = i
return X[k], Y[k]

# Przykład: D(-2,2), A(1,3), B(3,4), C(2,1)
X = [-2, 1, 3, 2]
Y = [2, 3, 4, 1]
print(skrajnie_lewy(X, Y)) # (-2, 2) - szczyt D

**Weryfikacja na przykładzie:**
- D: -2/2 = **-1.0** (najmniejszy)
- A: 1/3 ≈ 0.333
- B: 3/4 = 0.75
- C: 2/1 = 2.0

Minimum = -1.0 → D ✓

## Sposób 3 - C++ / Pascal

**C++ (bezpieczna wersja bez dzielenia float):**
```cpp
void skrajnieLewy(int X[], int Y[], int n, int& x, int& y) {
int k = 0;
for (int i = 1; i < n; i++) {
// X[i]/Y[i] < X[k]/Y[k] <=> X[i]*Y[k] < X[k]*Y[i] (Y[i], Y[k] > 0)
if ((long long)X[i] * Y[k] < (long long)X[k] * Y[i]) {
k = i;
}
}
x = X[k]; y = Y[k];
}

**Pascal:**
```pascal
procedure SkrajnieLewy(X, Y: array of LongInt; n: Integer; var x, y: LongInt);
var i, k: Integer;
begin
k := 0;
for i := 1 to n - 1 do begin
if X[i] * Y[k] < X[k] * Y[i] then k := i;
end;
x := X[k]; y := Y[k];
end;

## Reference informatyczny - wyszukiwanie minimum

> Reference - Wyszukiwanie minimum w tablicy:
> - Klasyczny algorytm O(n) z jedną zmienną przechowującą bieżące minimum.
> - Inicjalizacja: minimum = pierwszy element. Iteracja: porównanie z pozostałymi.
> - Tutaj funkcja porównująca to `X[i]/Y[i]`, czyli **funkcja klucza** (analogicznie do `key=` w Python `min()`).
>
> Reference - Porównanie ilorazów bez dzielenia:
> - `a/b < c/d` ⟺ `a·d < c·b` (gdy b, d > 0).
> - Zaleta: brak błędów zaokrąglenia floating-point.
> - Wada: ryzyko przepełnienia int (gdy `a·d` duże). W zadaniu Y > 0 zawsze, więc bezpiecznie.
>
> Reference - Interpretacja geometryczna:
> - Iloraz X/Y to **kąt nachylenia** linii od obserwatora (0,0) do punktu (X, Y).
> - Im mniejszy iloraz (ujemny dla X<0), tym bardziej w lewo.

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.1, max 2 pkt):
> - **1 pkt** za prawidłową inicjalizację (k = 1) ORAZ poprawną pętlę (dla i = 2, , n)
> - **1 pkt** za prawidłowe porównanie (X[i]/Y[i] < X[k]/Y[k]) ORAZ wyznaczenie wyniku (x, y)
> - **0 pkt** - odpowiedź błędna lub brak

## Typowe pułapki

- **Inicjalizacja k = 0** - w pseudokodzie CKE indeks startowy to 1, nie 0.
- **Wyszukiwanie maksimum** zamiast minimum - szczyt skrajnie LEWY to NAJMNIEJSZY iloraz X/Y.
- **Porównanie bezpośrednie X[i] < X[k]** - zła interpretacja "lewo" jako najmniejsze X. Trzeba uwzględnić Y.
- **Zwracanie indeksu** zamiast współrzędnych - pytanie pyta o (x, y), nie o k.
- **Float vs integer division** - w Pascal `/` zwraca Real, w C++ trzeba uważać przy int. Bezpieczniej mnożyć skrośnie.
- **Pominięcie warunku Y > 0** - w zadaniu Y jest dodatnie (z definicji), więc krzyżowe mnożenie bezpieczne.

## Złożoność obliczeniowa

- Jedno przejście przez tablicę: **O(n)** porównań.
- Pamięć: **O(1)** dodatkowa (tylko zmienna k).
- **Optymalne** - nie da się znaleźć minimum w mniej niż O(n) (każdy element trzeba sprawdzić).

## Linki

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

## Podobne zadania

- [Zadanie 3](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/3) — Zadanie 3. Pary slow W pliku tekstowym pary.txt znajduje sie 500 par slow zlozonych z liter alfabetu angielskiego a, b, , z. Kazda para slow jest zapisana w oso
- [Zadanie 2](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/2) — Zadanie 2. Dodawanie Rozwazamy dodawanie pisemne dwoch liczb zapisanych w systemie dziesietnym, zilustrowane na przykladzie. Przeniesienie: 1 1 1 1 Liczba a: 2 
- [Zadanie 4.2](https://matura.lol/question/informatyka-2020-lipiec-matura-rozszerzona-2/zad/4.2) — Zadanie 4.2. (0-4) Podaj wszystkie te identyfikatory dokumentów z pliku identyfikator.txt, których seria lub numer są palindromami, czyli czytane od lewej do pr
- [Zadanie 4.2](https://matura.lol/question/informatyka-2018-maj-matura-rozszerzona-2/zad/4.2) — Kontekst - patrz zadanie 4.1. Znajdź słowo, w którym występuje największa liczba **różnych** liter. Wypisz to słowo i liczbę występujących w nim różnych liter. 

_Ostatnia aktualizacja danych: 2026-10-03_