Matura z informatyki 2021 – arkusz próbny CKE, poziom rozszerzony

W turnieju siatkówki bierze udział n drużyn ponumerowanych kolejnymi liczbami całkowitymi od 0 do n − 1, gdzie n = 2^k dla pewnej liczby całkowitej k > 0. Turniej odbywa się w rundach systemem pucharowym – przegrywający odpada z turnieju. W każdej rundzie drużyny grają w parach i do dalszej rundy przechodzi tylko zwycięzca meczu. W każdej rundzie mecze są ponumerowane kolejnymi liczbami całkowitymi, poczynając od 1. W pierwszej rundzie w meczu nr 1 grają drużyny 0 i 1, w meczu nr 2 – drużyny 2 i 3, w meczu nr 3 – drużyny 4 i 5, w meczu nr i – drużyny 2(i − 1) oraz 2(i − 1)+1, itd. W każdej z kolejnych rund w meczu nr 1 grają zwycięzcy meczów o numerach 1 i 2 z poprzedniej rundy, w meczu nr 2 – zwycięzcy meczów o numerach 3 i 4 z poprzedniej rundy, w meczu nr i – zwycięzcy meczów o numerach 2i − 1 oraz 2i z poprzedniej rundy itd. Turniej trwa dokładnie k rund.

Przykład

Przykładową rozgrywkę w turnieju 8-drużynowym przedstawiono w postaci drzewa na rysunku poniżej. Na najniższym poziomie rysunku drzewa zapisano numery drużyn, natomiast w węzłach wewnętrznych – numery zwycięskich drużyn w poszczególnych meczach. Zwycięzcą turnieju została drużyna nr 6, która w meczu finałowym pokonała drużynę o numerze 2.

Numer rundy, w której mogą zmierzyć się dwie drużyny o numerach x i y, można wyznaczyć z zapisów binarnych liczb x i y o długości k (liczba rund). Twoim zadaniem jest odkrycie tej zależności.

Przykładowe rozwiązanie 1.

funkcja dwojkowe(a,k)
    A[0..k-1] – tablica
    dla i = 0, 1, ..., k-1
        A[k-i-1] ← a mod 2
        a ← a div 2
    podaj wynik A

X ← dwojkowe(x,k)
Y ← dwojkowe(y,k)
runda ← k
dla i = 0, 1, ..., k-1
    jeżeli X[i] = Y[i]
        runda ← runda - 1
    w przeciwnym razie
        przerwij pętlę
podaj wynik runda

Przykładowe rozwiązanie 2.

Możliwe jest też bardzo krótkie rozwiązanie bez wyliczania postaci dwójkowych explicite, na przykład:

runda ← 0
dopóki x ≠ y powtarzaj
    runda ← runda +1
    x ← x/2
    y ← y/2
podaj wynik runda

Wykonaj analizę funkcji Algo(n), której argumentem jest dodatnia liczba całkowita n.

Algo(n)
    jeżeli n ≤ 2 to
        wynikiem jest 1
    w przeciwnym przypadku
        p ← 1
        k ← n
        dopóki k − p > 1 wykonuj
            s ← (p + k) div 2
            jeżeli s * s ≤ n to
                p ← s
            w przeciwnym przypadku
                k ← s
        wynikiem jest p

Uwaga: div oznacza dzielenie całkowite.

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.

Firma Igloo planuje w wybranych miastach Europy wybudować galerie handlowe. W każdej z planowanych galerii może znajdować się różna liczba lokali handlowych. Wszystkie lokale handlowe będą miały kształt prostokąta.

W pliku galerie.txt zapisanych jest 50 wierszy z informacjami dotyczącymi planowanych galerii. Każdy wiersz w pliku to informacja o jednej galerii. Dane oddzielone są spacją i zawierają odpowiednio:

• kod kraju;
• nazwę miasta (nazwy miast nie powtarzają się);
• 70 par liczb (140 liczb) określających wymiary (długość i szerokość w metrach) lokali handlowych, które znajdować się będą w danej galerii. Jeżeli liczba lokali w galerii jest mniejsza niż 70, to wiersz uzupełniony jest zerami.

Przykład:

NL Amsterdam 8 4 5 12 7 5 5 11 9 4 7 6 … 0 0 0 0 0 0

Do Twojej dyspozycji jest pomocniczy plik galerie_przyklad.txt, zawierający 10 wierszy, który możesz wykorzystać, aby sprawdzić poprawność działania swojego(-ich) programu(-ów).

Napisz program(-y), w wyniku działania którego(-ych) otrzymasz odpowiedzi do podanych zadań. Pliki źródłowe z rozwiązaniem zapisz pod nazwą zgodną z numerem zadania, z rozszerzeniem odpowiadającym użytemu narzędziu informatycznemu.

H 1
I 2
F 1
GB 1
D 3
NL 1
DK 1

GB 5
D 15
E 6
I 6
F 2
RO 1
A 1
H 1
BG 1
CZ 1
B 1
S 1
HR 1
NL 2
LV 1
GR 1
LT 1
FIN 1
DK 1
IRL 1

Budapeszt 3598 64
Neapol 3352 48
Marsylia 3444 56
Leeds 2952 44
Frankfurt 3515 57
Genua 3386 56
Dortmund 3697 57
Rotterdam 3184 49
Dusseldorf 3737 63
Kopenhaga 3765 60

Kopenhaga 3765
Leeds 2952

Dusseldorf 34
Genua 23

Berlin 35
Kolonia 18

W pewnym kraju firma codziennie wykonuje wiele telefonów do swoich kontrahentów. W pliku telefony.txt znajduje się 2148 wierszy z danymi dotyczącymi połączeń wykonanych w lipcu 2017 roku. W każdym wierszu są podane dane, oddzielone pojedynczą spacją, opisujące jedno połączenie: numer telefonu, data wykonania połączenia, dokładna godzina rozpoczęcia i dokładna godzina zakończenia połączenia (w formacie godz:min:sek). Rodzaje numerów telefonów są rozpoznawane po liczbie cyfr:

• telefony stacjonarne są siedmiocyfrowe (w przykładzie pierwszy numer),
• telefony komórkowe – ośmiocyfrowe (w przykładzie drugi numer),
• zagraniczne – dziesięciocyfrowe lub dłuższe (w przykładzie trzeci numer).

Przykład:

nr data rozpoczecie zakonczenie
3539762 3-07-2017 08:04:54 08:21:26
54586484 3-07-2017 08:18:16 08:23:34
2109147679 3-07-2017 09:36:31 09:52:48

Korzystając z dostępnych narzędzi informatycznych, wykonaj poniższe polecenia. Odpowiedzi zapisz w pliku tekstowym wyniki5.txt, a każdą z nich poprzedź numerem zadania.

Pewien kibic zapisywał sobie w plikach tekstowych informacje o zawodnikach startujących w corocznym wyścigu kolarskim wraz z wynikami ich startów.

Wszystkie dane w plikach zawierają wiersze nagłówkowe z nazwami kolumn, natomiast dane w wierszach są rozdzielone znakami tabulacji.

W pliku grupy.txt znajdują się opisy grup kolarskich, których zawodnicy uczestniczyli w przynajmniej jednym wyścigu. Każdy wiersz zawiera kolejno:

• kod_grupy – trzyznakowy kod grupy kolarskiej,
• nazwa – nazwę grupy kolarskiej,
• siedziba – państwo, w którym grupa ma swoją siedzibę.

Fragment pliku grupy.txt:

kod_grupy    nazwa            siedziba
AGR          Agritubel        Francja
ALM          Ag2r-La Mondiale Francja

W pliku zawodnicy.txt znajdują się dane kolarzy, którzy uczestniczyli w przynajmniej jednym z wyścigów. Każdy wiersz zawiera kolejno:

• id_zawodnika – identyfikator zawodnika (liczba całkowita),
• imie – imię zawodnika,
• nazwisko – nazwisko zawodnika,
• data – datę urodzenia zawodnika w formacie rrrr-mm-dd.

Fragment pliku zawodnicy.txt:

id_zawodnika  imie    nazwisko  data
1             Janier  Acevedo   1985-12-06
2             Mario   Aerts     1974-12-31

W pliku startujacy.txt znajdują się dane kolarzy związane z ich startami w kolejnych edycjach wyścigu, każdy wiersz zawiera kolejno:

• id_startu – identyfikator startu (liczba całkowita),
• rok – rok edycji wyścigu,
• id_zawodnika – identyfikator zawodnika (liczba całkowita),
• kod_grupy – trzyznakowy kod grupy kolarskiej,
• obywatel_kraju – kraj, którego obywatelem był zawodnik podczas danej edycji wyścigu.

Fragment pliku startujacy.txt:

id_startu  rok   id_zawodnika  kod_grupy  obywatel_kraju
1          2008  176           TNK        Australia
2          2008  2             TNK        Belgia

W pliku czasy.txt znajdują się wyniki tylko tych kolarzy, którzy ukończyli wyścig. Każdy wiersz zawiera kolejno:

• id_startu – identyfikator startu (liczba całkowita),
• czas – czas osiągnięty przez zawodnika z uwzględnieniem wszystkich bonifikat zapisany w formacie mm:ss:ms.

Fragment pliku czasy.txt:

id_startu  czas
1          87:53:50
2          88:41:50

Korzystając z dostępnych narzędzi informatycznych, wykonaj poniższe polecenia. Odpowiedzi zapisz w pliku wyniki6.txt, a każdy podpunkt poprzedź odpowiadającym mu numerem zadania.

Chris Froom – Kenia, Wielka Brytania
Heinrich Haussler – Australia, Niemcy