Matura z informatyki 2015 – maj, poziom rozszerzony

W Problemie telewidza mamy program telewizyjny, zawierający listę filmów emitowanych w różnych stacjach telewizyjnych jednego dnia. Telewidz zamierza obejrzeć jak najwięcej filmów w całości. Jedyne ograniczenie jest takie, że telewidz może oglądać co najwyżej jeden film (stację telewizyjną) jednocześnie. Zakładamy, że jednego dnia wszystkie filmy są różne.

Program telewizyjny emisji filmów w 4 stacjach telewizyjnych:

Dla programu podanego powyżej telewidz jest w stanie obejrzeć aż trzy filmy, np.: film 1, film 4, film 2. Przyjmujemy, że telewidz nie traci w ogóle czasu na przełączanie pomiędzy stacjami (np. o godz. 12:00 z TV1 na TV3). Innymi słowy, czasy emisji filmów 1 i 4 nie kolidują ze sobą.

Rozważ następujący algorytm wyboru filmów do obejrzenia przez telewidza, w którym w kroku 2. stosuje się jedną z czterech strategii opisanych w tabeli 1.

Algorytm:

Krok 1.    Zainicjuj P jako zbiór pusty.
Krok 2.    Dopóki T zawiera jakieś filmy, wykonuj:
               . stosując strategię S, wybierz ze zbioru T film x i usuń go z T
               . dodaj film x do zbioru P
               . usuń ze zbioru T wszystkie filmy, których czasy emisji kolidują z czasem
                 emisji filmu x.
Krok 3.    Zakończ wykonywanie algorytmu i wypisz wszystkie filmy ze zbioru P.

Tabela 1. Cztery strategie (S) w Problemie telewidza:

Przykład:

Dla podanego programu telewizyjnego zastosowanie w kroku 2. strategii A daje wynik P = {film 3}, czyli telewidz obejrzy tylko jeden film.

Oceń, czy poniższe zdania są prawdziwe. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli zdanie jest fałszywe.

W każdym zadaniu punkt uzyskasz tylko za komplet poprawnych odpowiedzi.

Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych a > 0 i b ≥ 0.

Algorytm NWD:

Krok 1.    Jeżeli b = 0, to NWD jest równy a i zakończ wykonywanie algorytmu.
Krok 2.    Oblicz r jako resztę z dzielenia a przez b.
Krok 3.    Zastąp a przez b, natomiast b przez r.
Krok 4.    Przejdź do kroku 1.

W niektórych zastosowaniach informatycznych potrzebujemy wyrazić największy wspólny dzielnik dwóch liczb całkowitych a, b w następujący sposób:

NWD(a, b) = a · x + b · y,

gdzie x i y są liczbami całkowitymi.

Do wyznaczenia wartości x i y wykorzystywana jest następująca zależność:

dla r = a mod b różnego od zera oraz liczb całkowitych x', y' takich, że

NWD(b, r) = b · x' + r · y',

parę liczb (x, y) można wyrazić wzorami:

x = y'

y = x' – (a div b) · y'

Uwaga:

a mod b, a div b oznaczają odpowiednio resztę i iloraz z dzielenia całkowitego a przez b.

Opisana zależność pozwala na rekurencyjne obliczenie pary liczb (x, y). Niech RozszerzonyEuklides(a, b) będzie rekurencyjną funkcją realizującą ten pomysł. Działanie funkcji zilustrujmy przykładem.

Przykład dla a = 231, b = 30

Zatem NWD(231, 30) = 3 · 231 + (−23) · 30.

RozszerzonyEuklides(a, b):
Krok 1.    Jeśli b = 0, podaj jako wynik funkcji parę (1, 0) i zakończ jej wykonywanie.
Krok 2.    r ← a mod b
Krok 3.    (x, y) ← RozszerzonyEuklides(  ,  )
Krok 4.    Podaj jako wynik parę (  ,  ).

W pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie. Każda liczba zapisana jest w osobnym wierszu. Pierwsze pięć wierszy zawiera następujące liczby:

11010100111
11110111111011101
1010100111010100
1101111111111111111111010100101010101001
1010110011001101010011110101010101010111

Każda liczba binarna zawiera co najwyżej 250 cyfr binarnych, co oznacza, że w wielu językach programowania wartości niektórych z tych liczb nie da się zapamiętać w pojedynczej zmiennej typu całkowitoliczbowego, np. w języku C++ w zmiennej typu int.

Napisz program, który da odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wynik4.txt, a każdą odpowiedź poprzedź numerem oznaczającym odpowiednie zadanie.

101011010011001100111
10001001
1000000
101010011100
100010

101011010011001100000 (*), (**)
10001001
100100 (*)
101010010101011011000 (*), (**)
100011

101011010011001100111
10001001011101010
1001000
101010011100
1000110

W kolejnych wierszach pliku kraina.txt znajdują się dane demograficzne Edulandii, która składa się z 50 województw. Każde z województw znajduje się w jednym z 4 regionów: A, B, C lub D. Każdy wiersz zawiera oddzielone średnikami informacje o jednym województwie, w następującej kolejności: nazwa województwa, liczba kobiet w 2013 roku, liczba mężczyzn w 2013 roku, liczba kobiet w 2014 roku, liczba mężczyzn w 2014 roku.

Przykład:

w01D;1415007;1397195;1499070;1481105
w02D;1711390;1641773;1522030;1618733
w03C;1165105;1278732;1299953;1191621
w04D;949065;1026050;688027;723233

Nazwa każdego województwa zaczyna się literą „w", za nią występuje dwucyfrowy numer województwa, a na końcu litera A, B, C lub D oznaczająca region, w którym to województwo się znajduje.

Korzystając z dostępnych narzędzi informatycznych, podaj odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wynik5.txt, a każdą odpowiedź poprzedź numerem oznaczającym to zadanie.

W następujących plikach zgromadzono dane dotyczące wyścigów samochodowych Formuły 1 z lat 2000–2012. Pierwszy wiersz w każdym z plików jest wierszem nagłówkowym i zawiera nazwy pól.

W pliku Kierowcy.txt każdy wiersz zawiera informacje o kierowcy, rozdzielone średnikami: Id_kierowcy, Nazwisko, Imie, Kraj.

Przykład:

z10;Irvine;Eddie;Irlandia

W pliku Wyscigi.txt są zawarte informacje o rozegranych wyścigach Grand Prix liczonych do klasyfikacji generalnej: Id_wyscigu, Rok, GrandPrix. Sezon jest reprezentowany przez rok (czterocyfrowa liczba), a GrandPrix jest nazwą miejsca, w którym jest rozgrywany wyścig.

Przykład:

w20;2001;Brazylia

W pliku Wyniki.txt każdy wiersz zawiera informacje o punktach zdobytych przez kierowców w poszczególnych wyścigach, rozdzielone średnikami: Id_kierowcy, Punkty, Id_wyscigu.

Przykład:

z42;6;w7

Wykorzystując dane zawarte w plikach Kierowcy.txt, Wyscigi.txt i Wyniki.txt, wykonaj poniższe polecenia, a odpowiedzi poprzedzone numerem oznaczającym podpunkt zapisz w pliku wynik6.txt.