Matura informatyka

Przykładowy arkusz CKE — formuła 2023

PythonC++23Java 25
Treść zadania

Plik szachy.txt zawiera opisy 125 plansz (stanów partii szachowej). Każda plansza to 8 wierszy po 8 znaków: . — puste pole, wielkie litery — białe bierki, małe — czarne (K/k — król, H/h — hetman, W/w — wieża, G/g — goniec, S/s — skoczek, P/p — pionek). Po każdej planszy jest pusty wiersz. Plik szachy_przyklad.txt zawiera 9 plansz. Znajomość reguł szachów nie jest potrzebna.

  • 1.1 — Podaj, na ilu planszach jest co najmniej jedna pusta kolumna, oraz największą liczbę pustych kolumn na jednej planszy. Wynik (dwie liczby oddzielone spacją) zapisz w zadanie1_1.txt (przykład: 7 5).
  • 1.2 — Plansza jest w równowadze, gdy białe i czarne mają dokładnie te same bierki w tych samych liczbach. Podaj liczbę takich plansz i najmniejszą łączną liczbę bierek na planszy w równowadze; zapisz w zadanie1_2.txt (przykład: 6 4).
  • 1.3 — Wieża szachuje króla przeciwnika, gdy stoi z nim w tym samym wierszu lub kolumnie i nie ma między nimi innej bierki. Podaj, na ilu planszach biała wieża szachuje czarnego króla, a na ilu czarna wieża szachuje białego; zapisz w zadanie1_3.txt (przykład: 2 0).
Python
def wczytaj_plansze(nazwa):
    plansze = []
    with open(nazwa) as file:
        wiersze = [linia.strip() for linia in file]
    for i in range(0, len(wiersze), 9):
        if len(wiersze[i:i + 8]) == 8 and wiersze[i]:
            plansze.append(wiersze[i:i + 8])
    return plansze


plansze = wczytaj_plansze("szachy.txt")

# 1.1
ile_plansz = 0
max_pustych = 0
for p in plansze:
    puste = 0
    for k in range(8):
        if all(p[w][k] == "." for w in range(8)):
            puste += 1
    if puste > 0:
        ile_plansz += 1
        max_pustych = max(max_pustych, puste)
print("1.1", ile_plansz, max_pustych)

# 1.2
ile_rownowag = 0
min_bierek = 64
for p in plansze:
    biale = []
    czarne = []
    for wiersz in p:
        for znak in wiersz:
            if znak.isupper():
                biale.append(znak)
            elif znak.islower():
                czarne.append(znak.upper())
    if sorted(biale) == sorted(czarne):
        ile_rownowag += 1
        min_bierek = min(min_bierek, len(biale) + len(czarne))
print("1.2", ile_rownowag, min_bierek)


# 1.3
def szachuje(p, wieza, krol):
    # czy jakaś wieża (znak wieza) szachuje króla (znak krol)
    for w in range(8):
        for k in range(8):
            if p[w][k] != wieza:
                continue
            for dw, dk in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                x, y = w + dw, k + dk
                while 0 <= x < 8 and 0 <= y < 8 and p[x][y] == ".":
                    x, y = x + dw, y + dk
                if 0 <= x < 8 and 0 <= y < 8 and p[x][y] == krol:
                    return True
    return False


biala = 0
czarna = 0
for p in plansze:
    if szachuje(p, "W", "k"):
        biala += 1
    if szachuje(p, "w", "K"):
        czarna += 1
print("1.3", biala, czarna)

Odpowiedź: 1.1: 36 3. 1.2: 22 28. 1.3: 3 1.

↑
PythonC++23Java 25
Treść zadania

Plansza B ma pola 0..s; na początku pionek stoi tylko na B[0]. Gra składa się z n tur opisanych tablicą A[1..n] dodatnich liczb całkowitych. W k-tej turze:

Kod
Tura(k):
    dla i = s, s-1, ..., A[k]
        jeśli na B[i - A[k]] stoi pionek i B[i] jest puste
            postaw pionek na B[i]

Gra kończy się sukcesem, gdy po n turach pionek stoi na B[s].

  • 2.1 — Rozstrzygnij (TAK/NIE), czy gra kończy się sukcesem dla: A = [1, 2, 5, 10], s = 14; A = [13, 5, 5, 2, 7], s = 17; A = [7, 6, 5, 4, 3, 2, 1], s = 25 (np. A = [1, 2, 3], s = 5 → TAK).
  • 2.2 — Dla A = [5, 10, 15, ..., 100] i s = 500 podaj, na ilu polach będą stały pionki po zakończeniu gry.
  • 2.3 — Podaj przykładową tablicę A o co najwyżej 10 elementach, dla której gra kończy się sukcesem dla każdego s = 1, 2, ..., 200.
Python
def gra(A, s):
    B = [False] * (s + 1)
    B[0] = True
    for a in A:  # Tura(k)
        for i in range(s, a - 1, -1):
            if B[i - a] and not B[i]:
                B[i] = True
    return B


# 2.1
for A, s in [([1, 2, 3], 5), ([1, 2, 5, 10], 14), ([13, 5, 5, 2, 7], 17), ([7, 6, 5, 4, 3, 2, 1], 25)]:
    print("2.1", A, s, "TAK" if gra(A, s)[s] else "NIE")

# 2.2
A = list(range(5, 101, 5))
print("2.2", sum(gra(A, 500)))

# 2.3 - sprawdzenie przykładowej odpowiedzi
A = [1, 2, 4, 8, 16, 32, 64, 128]
print("2.3", all(gra(A, s)[s] for s in range(1, 201)))

Odpowiedź: 2.1: TAK (dane), NIE, TAK, TAK. 2.2: 101 (pola B[0], B[5], …, B[500]). 2.3: np. A = [1, 2, 4, 8, 16, 32, 64, 128] (każde s od 1 do 255 da się zapisać jako sumę różnych potęg dwójki).

↑
PythonC++23Java 25
Treść zadania

Potęgowanie modularne: b = a^x mod M (a, M — dodatnie, x — nieujemna liczba całkowita). Np. 2^5 mod 7 = 4.

  • 3.1 — Uzupełnij brakującą liczbę (x lub b) w wierszach: M = 11, a = 3, x = 3; M = 31, a = 5, b = 25; M = 59, a = 2, b = 5.
  • 3.2 — Zapisz algorytm obliczający a^x mod M wykonujący O(log x) operacji (dozwolone tylko podstawowe operacje arytmetyczne, porównania, instrukcje sterujące).

Plik liczby.txt ma 1000 wierszy, w każdym trzy liczby M, a, b (≤ 10 000; M, a ≥ 2) oddzielone spacjami. Odpowiedzi do 3.3–3.5 zapisz w wyniki3.txt z numerami zadań (przykład: liczby_przyklad.txt, 5 wierszy).

  • 3.3 — Podaj, w ilu wierszach M jest liczbą pierwszą (przykład: 2).
  • 3.4 — Podaj, w ilu wierszach M i a są względnie pierwsze (przykład: 3).
  • 3.5 — Podaj, dla ilu trójek (M, a, b) istnieje x z przedziału [0, M−1] takie, że a^x mod M = b (przykład: 4).
Python
def potega_mod(a, x, M):
    # szybkie potęgowanie modularne - O(log x) mnożeń
    wynik = 1
    a = a % M
    while x > 0:
        if x % 2 == 1:
            wynik = wynik * a % M
        a = a * a % M
        x = x // 2
    return wynik


def czy_pierwsza(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


def nwd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


# 3.1
print("3.1", potega_mod(3, 3, 11), potega_mod(9, 2, 80))
for M, a, b in [(31, 5, 25), (59, 2, 5)]:
    x = 0
    while potega_mod(a, x, M) != b:
        x += 1
    print("3.1 x =", x)

trojki = []
with open("liczby.txt") as file:
    for linia in file:
        M, a, b = map(int, linia.split())
        trojki.append((M, a, b))

# 3.3
print("3.3", sum(1 for M, a, b in trojki if czy_pierwsza(M)))

# 3.4
print("3.4", sum(1 for M, a, b in trojki if nwd(M, a) == 1))

# 3.5
ile = 0
for M, a, b in trojki:
    potega = 1 % M  # a^0 mod M
    for x in range(M):
        if potega == b:
            ile += 1
            break
        potega = potega * a % M
print("3.5", ile)

Odpowiedź: 3.1: b = 5 (M = 11), x = 2 (M = 31), x = 6 (M = 59), b = 1 (M = 80). 3.2: funkcja potega_mod (szybkie potęgowanie, O(log x)). 3.3: 343. 3.4: 712. 3.5: 764.

↑

Edytuj na GitHubie