Matura informatyka

Matura próbna 2022 — grudzień (formuła 2023)

PythonC++23Java 25

Treść zadania (Kosmiczny mecz): Plik mecz.txt zawiera jeden wiersz – napis z 10 000 znaków A i B opisujący wyniki kolejnych rozgrywek meczu (znak oznacza drużynę, która wygrała daną rozgrywkę i zdobyła punkt). Odpowiedzi zapisz w pliku wyniki1.txt, poprzedzając każdą numerem zadania (plik mecz_przyklad.txt służy do testów).

  • 1.1 — Policz, ile razy rozgrywkę wygrała inna drużyna niż poprzednią (dwa kolejne znaki są różne). Przykład: dla ABBBABA odpowiedź to 4; dla pliku przykładowego – 1798.
  • 1.2 — Pierwszy set trwa do pierwszej rozgrywki, po której jedna z drużyn ma co najmniej 1000 punktów, a przeciwna co najmniej 3 punkty mniej (np. 1000:500, 997:1000, 1500:1497 kończą seta; 999:1000 czy 1500:1500 nie). Podaj zwycięzcę pierwszego seta i wynik w tym momencie (punkty A : punkty B). Dla pliku przykładowego: A 1000:5.
  • 1.3 — Dobra passa to co najmniej 10 wygranych z rzędu jednej drużyny (maksymalny ciąg – zaczyna się na początku meczu lub po przegranej i kończy z końcem meczu lub przed przegraną). Podaj łączną liczbę dobrych pass obu drużyn oraz długość najdłuższej passy i drużynę, która ją osiągnęła (jest jedna taka). Przykład: w BBBBBBBBBBAABBAAAAAAAAAAABA są 2 dobre passy, najdłuższa ma długość 11 (drużyna A).
Python
with open("mecz.txt") as file:
    mecz = file.readline().strip()

# 1.1
zmiany = 0
for i in range(1, len(mecz)):
    if mecz[i] != mecz[i - 1]:
        zmiany += 1
print("1.1", zmiany)

# 1.2
punkty_a = 0
punkty_b = 0
for znak in mecz:
    if znak == "A":
        punkty_a += 1
    else:
        punkty_b += 1
    if (punkty_a >= 1000 or punkty_b >= 1000) and abs(punkty_a - punkty_b) >= 3:
        break
if punkty_a > punkty_b:
    print("1.2", "A", str(punkty_a) + ":" + str(punkty_b))
else:
    print("1.2", "B", str(punkty_a) + ":" + str(punkty_b))

# 1.3 - dzielimy mecz na maksymalne bloki jednakowych znaków
dobre_passy = 0
najdluzsza = 0
druzyna = ""
dlugosc = 1
for i in range(1, len(mecz) + 1):
    if i < len(mecz) and mecz[i] == mecz[i - 1]:
        dlugosc += 1
    else:
        # koniec bloku mecz[i - dlugosc .. i - 1]
        if dlugosc >= 10:
            dobre_passy += 1
            if dlugosc > najdluzsza:
                najdluzsza = dlugosc
                druzyna = mecz[i - 1]
        dlugosc = 1
print("1.3", dobre_passy, druzyna, najdluzsza)

Odpowiedź: 1.1: 5030; 1.2: B 1001:1004; 1.3: 6 B 15

↑
PythonC++23Java 25

Treść zadania (Strzałki): Dla dodatniego N rysujemy punkty o numerach 1..N. Funkcja strzałka(x, y) rysuje strzałkę z punktu x do y, a rekurencyjna funkcja rysuj(x) działa tak:

Kod
funkcja rysuj(x)
  jeżeli 2*x ≤ N:     strzałka(x, 2*x);     rysuj(2*x)
  jeżeli 2*x+1 ≤ N:   strzałka(x, 2*x+1);   rysuj(2*x+1)
  • 2.1 — Dla N = 10 narysuj punkty 1..10 i strzałki powstałe po wywołaniu rysuj(1).
  • 2.2 — Podaj, ile strzałek zostanie narysowanych po wywołaniu rysuj(1): a) dla N = 20, b) dla dowolnego N.
  • 2.3 — Dla N = 2047 podaj, po ilu strzałkach (zgodnie z ich zwrotem) trzeba przejść z punktu 1 do punktu N (dla N = 5 z punktu 1 do 5 – po dwóch).
  • 2.4 — Plik pary.txt zawiera 1000 par liczb całkowitych z zakresu [1, 100 000] (w wierszu, oddzielone spacją; druga liczba jest większa od pierwszej). Napisz program, który wypisze te pary (x, y), dla których z punktu x da się dojść do punktu y po jednej lub kilku strzałkach zgodnie z ich zwrotami (np. z 1 do 4 – tak, z 3 do 5 – nie). Wynik zapisz w wyniki2.txt.
Python
strzalki = []


def rysuj(x, N):
    if 2 * x <= N:
        strzalki.append((x, 2 * x))
        rysuj(2 * x, N)
    if 2 * x + 1 <= N:
        strzalki.append((x, 2 * x + 1))
        rysuj(2 * x + 1, N)


# 2.1 - lista strzałek dla N = 10 (punkt x łączy się z 2x i 2x+1 - drzewo binarne)
rysuj(1, 10)
print("2.1", strzalki)

# 2.2 - każdy punkt poza 1 ma dokładnie jedną strzałkę wchodzącą (od x // 2)
strzalki = []
rysuj(1, 20)
print("2.2", len(strzalki), "ogólnie N - 1")

# 2.3 - idąc od N do 1 przechodzimy do N // 2
N = 2047
kroki = 0
while N > 1:
    N //= 2
    kroki += 1
print("2.3", kroki)


# 2.4 - z x da się dojść do y, gdy dzieląc y przez 2 (całkowicie) dojdziemy do x
def osiagalny(x, y):
    while y > x:
        y //= 2
    return x == y


print("2.4")
with open("pary.txt") as file:
    for line in file:
        x, y = map(int, line.split())
        if osiagalny(x, y):
            print(x, y)

Odpowiedź: 2.1: strzałki 1→2, 1→3, 2→4, 2→5, 3→6, 3→7, 4→8, 4→9, 5→10; 2.2: a) 19, b) N − 1; 2.3: 10; 2.4: 47 3044, 7650 61204, 1 245, 7 63669, 9125 18250, 5 43246

↑
PythonC++23Java 25

Treść zadania (Liczby):

  • 3.1 — Uzupełnij luki w algorytmie sita Eratostenesa, który dla N > 1 wypełnia tablicę logiczną SITO[1..N] (PRAWDA dla liczb pierwszych, FAŁSZ dla złożonych):
Kod
SITO[1] ← FAŁSZ
dla i = 2, ..., N:  SITO[i] ← PRAWDA
dla i = 2, 3, ..., ____
  jeżeli SITO[i] = ____
    j ← ____
    dopóki j ≤ N:  SITO[j] ← ____;  j ← ____

Plik liczby.txt zawiera 100 liczb parzystych z zakresu [4, 1 000 000], po jednej w wierszu. Odpowiedzi do 3.2–3.4 zapisz w wyniki3.txt z numerem zadania (do testów: liczby_przyklad.txt).

  • 3.2 — Podaj, dla ilu liczb x z pliku liczba x − 1 jest pierwsza.
  • 3.3 — Dla każdej liczby wyznacz, na ile sposobów da się ją zapisać jako sumę dwóch liczb pierwszych (rozkłady różniące się tylko kolejnością składników są takie same, np. 22 = 19 + 3 = 17 + 5 = 11 + 11). Podaj liczbę o największej liczbie rozkładów wraz z tą liczbą oraz liczbę o najmniejszej liczbie rozkładów wraz z tą liczbą. Dla pliku przykładowego: 996 37 4 1.
  • 3.4 — Zapisz każdą liczbę w systemie szesnastkowym i dla każdej cyfry 0–F podaj, ile razy łącznie występuje we wszystkich tych zapisach (w formacie cyfra:liczba, np. 0:2, 1:3, …).
Python
# 3.1 - sito Eratostenesa (luki: N (wystarczy pierwiastek z N), PRAWDA, i * i, FAŁSZ, j + i)
def sito(N):
    SITO = [True] * (N + 1)
    SITO[0] = False
    SITO[1] = False
    i = 2
    while i * i <= N:
        if SITO[i]:
            j = i * i
            while j <= N:
                SITO[j] = False
                j = j + i
        i += 1
    return SITO


liczby = []
with open("liczby.txt") as file:
    for line in file:
        liczby.append(int(line))

SITO = sito(1000000)

# 3.2
ile = 0
for x in liczby:
    if SITO[x - 1]:
        ile += 1
print("3.2", ile)

# 3.3 - rozkład x = p + (x - p), p <= x - p
najwiecej, liczba_max = -1, 0
najmniej, liczba_min = 10 ** 9, 0
for x in liczby:
    rozklady = 0
    for p in range(2, x // 2 + 1):
        if SITO[p] and SITO[x - p]:
            rozklady += 1
    if rozklady > najwiecej:
        najwiecej, liczba_max = rozklady, x
    if rozklady < najmniej:
        najmniej, liczba_min = rozklady, x
print("3.3", liczba_max, najwiecej, liczba_min, najmniej)

# 3.4
cyfry = "0123456789ABCDEF"
ile_cyfr = [0] * 16
for x in liczby:
    while x > 0:
        ile_cyfr[x % 16] += 1
        x //= 16
print("3.4")
for i in range(16):
    print(cyfry[i] + ":" + str(ile_cyfr[i]))

Odpowiedź: 3.1: luki kolejno: N (wystarczy √N), PRAWDA, i * i, FAŁSZ, j + i; 3.2: 21; 3.3: 910620 9932 18676 195; 3.4: 0:32, 1:26, 2:37, 3:31, 4:43, 5:25, 6:28, 7:23, 8:38, 9:28, A:45, B:33, C:29, D:23, E:44, F:10

↑

Edytuj na GitHubie