Matura z informatyki 2017 – czerwiec, poziom rozszerzony

Rozważmy następującą procedurę, której parametrem jest dodatnia liczba całkowita n.

Procedura Sitko(n)
dla i=1,2,…,n wykonuj
        Czyjest[i] ← fałsz
j ← 1
dopóki j*j < n wykonuj
        j ← j+1
dla i = 2,3,…,j wykonuj
        kw ← i * i
        poz ← kw
        dopóki poz ≤ n
        (*) Czyjest[poz] ← prawda
             poz ← poz + kw

Algorytm I
for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++)
                if (Czyjest[i] && Czyjest[j] && i+j==k)
                        return true
return false

Algorytm II
int i=1;
int j=n;
while (i<j)
        if (!Czyjest[i] || i+j<k)
                i+ = 1
        else
                if (!Czyjest[j] || i+j>k)
                        j– =1
                else
                        return true;
return false;

W tym zadaniu rozważamy tylko słowa zbudowane z wielkich liter A i B. Słowo nazwiemy palindromem, gdy czytane od lewej do prawej jest takie samo jak czytane od prawej do lewej. Przykładowo słowo ABABA jest palindromem, natomiast palindromem nie jest słowo BAABA. Dla słowa w definiujemy jego regularność reg(w), jak następuje:

• jeśli słowo w jest słowem jednoliterowym, to jest palindromem, a jego reg(w) = 1
• jeśli słowo w składa się z więcej niż jednej litery, to można je przedstawić w postaci: w=w₁Zw₂, gdy ma długość nieparzystą, lub w=w₁w₂, gdy ma długość parzystą, gdzie w₁, w₂ są słowami tej samej długości, a Z jest literą A lub literą B. Jeżeli w nie jest palindromem, definiujemy reg(w)=0, natomiast gdy w jest palindromem definiujemy reg(w)=reg(w₁)+1.

Przykład:

Funkcja REG(w,n)
    jeżeli n = 1
            wynikiem jest 
    w przeciwnym przypadku
            jeżeli n mod 2 = 0
                m ← n / 2
            w przeciwnym przypadku
                m ← (n - 1) / 2
            dla i=1,2,…,m wykonuj
                jeżeli w[i] ≠ 
                        podaj wynik 0 i zakończ wykonywanie funkcji
            x ← w[1..m]
            wynikiem jest 1 + 

W oddziałach światowej korporacji zegary podają liczbę minut, które upłynęły od początku doby. Wynik podawany jest w różnych systemach pozycyjnych:

• Oddział A: system binarny,
• Oddział B: system czwórkowy,
• Oddział C: system szesnastkowy.

Oddziały A, B i C znajdują się w różnych strefach czasowych, dlatego zegary nie wskazują tej samej liczby. W pewnym momencie zegary wskazywały następujące wartości:

• Oddział A: 00010110100,
• Oddział B: 000330,
• Oddział C: 078.

Plik punkty.txt zawiera 1000 wierszy, w których zapisane są po dwie liczby całkowite z przedziału [0, 10000], oddzielone pojedynczym odstępem. Para liczb w każdym wierszu odpowiada współrzędnym (x, y) jednego punktu w układzie kartezjańskim. W danych punkty nie powtarzają się.

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

Firma transportowa dysponuje samochodami ciężarowymi przeznaczonymi do realizacji usług dla klientów. Informacje o wszystkich samochodach tej firmy zapisano w pliku transport.txt.

Każdy samochód opisano w osobnym wierszu, podając: markę i model (łącznie jako jedno pole), rok produkcji, cenę zakupu w zł, numer rejestracyjny, przebieg w km oraz datę ostatniego remontu.

Dane w wierszu oddzielone są znakiem tabulacji. Pierwszy wiersz pliku jest wierszem nagłówkowym.

Przykład:

Samochód podlega amortyzacji na skutek zużycia oraz upływu czasu. Wartość samochodu obniża się

• o 5% ceny zakupu za każdy rok liczony od roku produkcji;
• o 2% ceny zakupu po przejechaniu każdych 100 000 km.

Przykład:

Wartość samochodu wyprodukowanego w 2015 roku zakupionego za 70 000 zł, w 2017 roku (po 2 latach od roku produkcji) i przebiegu 350 000 km wyniesie 58800 zł, ponieważ

• amortyzacja w wyniku upływu czasu obniży wartość samochodu o 7000 zł = 5%70000 2
• amortyzacja w wyniku zużycia obniży wartość samochodu o kolejne 4200 zł = 2%700003

Wykorzystaj dane zawarte w pliku transport.txt oraz dostępne narzędzia informatyczne i podaj odpowiedzi do poniższych zadań. Odpowiedzi umieść w pliku wyniki5.txt, a każdą odpowiedź poprzedź numerem oznaczającym to zadanie.

Sklep internetowy prowadzi sprzedaż programów komputerowych różnych firm. Większość oprogramowania oferowana jest w pakietach po kilka programów, ale trafiają się oferty programów pojedynczych.

Pierwszy wiersz w każdym z plików jest wierszem nagłówkowym i zawiera nazwy pól. Dane w każdym wierszu oddzielone są znakiem tabulacji.

W pliku programy.txt podano informacje o oferowanych programach: identyfikator programu, jego nazwę, rodzaj i cenę w zł, każdy program w osobnym wierszu pliku. Przykład:

W pliku pakiety.txt zapisano informacje o pakietach: identyfikator pakietu, jego nazwę oraz nazwę firmy producenta, każdy pakiet w osobnym wierszu. Przykład:

Plik zestawy.txt opisuje zawartość pakietów. W każdym wierszu znajdują się dwie liczby: identyfikator pakietu oraz identyfikator programu. Każdemu pakietowi odpowiada tyle wierszy w pliku, ile programów zawiera ten pakiet. Przykład:

Wykorzystując dane z plików oraz dostępne narzędzia informatyczne, podaj odpowiedzi do poniższych zadań. Odpowiedzi umieść w pliku wyniki6.txt, a każdą odpowiedź poprzedź numerem oznaczającym to zadanie.