Matura CKE Maj 2018 – Informatyka Rozszerzona

Zadanie 1. Analiza algorytmu
Rozważamy następujący algorytm:
Dane:
$n$ – liczba całkowita dodatnia
Wynik:
$p$ – liczba całkowita dodatnia
p ← 1
q ← n
dopóki p < q wykonuj
  s ← (p+q) div 2
  (*) jeżeli s*s*s < n wykonaj
      p ← s+1
    w przeciwnym wypadku
      q ← s
Uwaga: zapis div oznacza dzielenie całkowite.

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 ($x_A$, $y_A$) oraz ($x_B$, $y_B$), to mówimy, że:

• szczyt A jest dla obserwatora widoczny na lewo od B, jeśli $x_A/y_A < x_B/y_B$;
• szczyt B jest widoczny na lewo od A, jeśli $x_A/y_A > x_B/y_B$.

Wiemy, że żadne dwa szczyty nie leżą w jednej linii z obserwatorem, a zatem dla obserwatora te szczyty nie zasłaniają się nawzajem. Ilustrację przykładowego położenia szczytów można zobaczyć na poniższym rysunku:
W tym przykładzie, patrząc od lewej do prawej strony, obserwator widzi kolejno szczyt D, szczyt A, szczyt B i szczyt 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]$).

Zadanie 3. Test
Oceń prawdziwość podanych zdań. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli jest fałszywe.
W każdym zadaniu punkt uzyskasz tylko za komplet poprawnych odpowiedzi.