Matura informatyka

Matura 2024 — maj, poziom rozszerzony (formuła 2023)

PythonC++23Java 25
Treść zadania

Plansza ma n wierszy (numerowanych od góry 1..n) i m kolumn (numerowanych od lewej 1..m); każde pole jest białe albo czarne. Opisuje ją tablica A[1..n][1..m], w której A[i][j] = 1 oznacza pole białe, a 0 — czarne. Lewy górny i prawy dolny róg są zawsze białe. Algorytm korzysta z pomocniczej tablicy logicznej P[1..n][1..m] i zwraca PRAWDA albo FAŁSZ:

Kod
P[1][1] ← PRAWDA
dla i = 1, 2, ..., n wykonuj
    dla j = 1, 2, ..., m wykonuj
        jeżeli A[i][j] = 0
            P[i][j] ← FAŁSZ
        w przeciwnym przypadku
            jeżeli i = 1 oraz j ≠ 1:  P[i][j] ← P[i][j−1]
            jeżeli i ≠ 1 oraz j = 1:  P[i][j] ← P[i−1][j]
            jeżeli i ≠ 1 oraz j ≠ 1:  P[i][j] ← P[i][j−1] lub P[i−1][j]
podaj wynik P[n][m]
  • 1.1 — Podaj wynik algorytmu dla trzech plansz przedstawionych na rysunkach w arkuszu: a) 3 × 3, b) 5 wierszy × 3 kolumny, c) 5 × 5.
  • 1.2 — Podaj przykład planszy (z białymi narożnikami: lewym górnym i prawym dolnym): a) 5 × 5 z co najwyżej 2 czarnymi polami, dla której wynikiem jest FAŁSZ; b) 4 × 4 z co najmniej 9 czarnymi polami, dla której wynikiem jest PRAWDA.
  • 1.3 — Dla kwadratowej planszy n × n podaj największą możliwą liczbę czarnych pól, przy której algorytm zwraca PRAWDA.
Python
def algorytm(A):
    n = len(A)
    m = len(A[0])
    P = [[False] * m for _ in range(n)]
    P[0][0] = True
    for i in range(n):
        for j in range(m):
            if A[i][j] == 0:
                P[i][j] = False
            elif i == 0 and j != 0:
                P[i][j] = P[i][j - 1]
            elif i != 0 and j == 0:
                P[i][j] = P[i - 1][j]
            elif i != 0 and j != 0:
                P[i][j] = P[i][j - 1] or P[i - 1][j]
    return P[n - 1][m - 1]


# 1.1 (1 - pole białe, 0 - pole czarne)
a = [[1, 1, 1],
     [0, 1, 0],
     [1, 1, 1]]
b = [[1, 1, 1],
     [0, 0, 1],
     [1, 1, 1],
     [1, 0, 0],
     [1, 1, 1]]
c = [[1, 0, 0, 0, 0],
     [1, 1, 0, 0, 1],
     [0, 1, 0, 0, 1],
     [0, 1, 1, 1, 0],
     [0, 1, 0, 1, 1]]
for plansza in [a, b, c]:
    print(algorytm(plansza))

# 1.2 - sprawdzenie przykładowych plansz
a2 = [[1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1],
      [1, 1, 1, 1, 0],
      [1, 1, 1, 0, 1]]
b2 = [[1, 0, 0, 0],
      [1, 0, 0, 0],
      [1, 0, 0, 0],
      [1, 1, 1, 1]]
print(algorytm(a2), algorytm(b2))

# 1.3 - sprawdzenie wzoru (n-1)^2 dla małych plansz (przegląd wszystkich plansz)
for n in range(2, 5):
    najwiecej = 0
    for maska in range(2 ** (n * n)):
        A = [[0 if maska >> (i * n + j) & 1 else 1 for j in range(n)] for i in range(n)]
        if A[0][0] == 1 and A[n - 1][n - 1] == 1 and algorytm(A):
            czarne = sum(row.count(0) for row in A)
            najwiecej = max(najwiecej, czarne)
    print(n, najwiecej, (n - 1) ** 2)

Odpowiedź: 1.1: a) PRAWDA, b) FAŁSZ, c) PRAWDA. 1.2: algorytm zwraca PRAWDA wtedy i tylko wtedy, gdy istnieje ścieżka po białych polach z lewego górnego do prawego dolnego rogu, poruszając się tylko w prawo lub w dół; a) np. plansza 5 × 5 z czarnymi polami (4, 5) i (5, 4) — FAŁSZ; b) np. plansza 4 × 4, w której białe są tylko pierwsza kolumna i ostatni wiersz (9 pól czarnych) — PRAWDA. 1.3: (n − 1)² (ścieżka z rogu do rogu ma zawsze 2n − 1 białych pól, więc czarnych może być n² − (2n − 1)).

↑
PythonC++23Java 25
Treść zadania

Algorytm dla nieujemnej liczby całkowitej n oblicza liczbę c (mod i div to reszta i iloraz z dzielenia całkowitego):

Kod
b ← 1
c ← 0
dopóki n > 0 wykonuj
    a ← n mod 10
    n ← n div 10
    jeżeli a mod 2 = 0
        c ← c + b * (a div 2)
    w przeciwnym razie
        c ← c + b
    b ← b * 10
  • 2.1 — Uzupełnij tabelę: dla n = 542102 oraz n = 87654321012345678 podaj wartość c po zakończeniu algorytmu i liczbę wykonań instrukcji c ← c + b (przykład: dla n = 33658 jest c = 11314 i 3 wykonania).
  • 2.2 — Podaj wartość c dla osiemnastocyfrowej liczby n, której pierwsze sześć cyfr to 3, kolejne sześć to 6, a ostatnie sześć to 9.
Python
def algorytm(n):
    b = 1
    c = 0
    wykonania = 0
    while n > 0:
        a = n % 10
        n = n // 10
        if a % 2 == 0:
            c = c + b * (a // 2)
        else:
            c = c + b
            wykonania += 1
        b = b * 10
    return c, wykonania


# 2.1
for n in [33658, 542102, 87654321012345678]:
    print(n, *algorytm(n))

# 2.2
n = int("3" * 6 + "6" * 6 + "9" * 6)
print(algorytm(n)[0])

Odpowiedź: 2.1: 33658 → 11314, 3 wykonania; 542102 → 121101, 2 wykonania; 87654321012345678 → 41312111011121314, 8 wykonań. 2.2: c = 111111333333111111.

↑
PythonC++23Java 25
Treść zadania

Nieparzystym skrótem dodatniej liczby całkowitej n jest liczba m powstała przez usunięcie z zapisu dziesiętnego n wszystkich cyfr parzystych. Jeśli n ma same cyfry parzyste, skrót nie istnieje. Przykłady: skrót 294762 to 97, skrót 39101 to 3911, skrót 224 nie istnieje.

Napisz (w pseudokodzie lub wybranym języku) funkcję, która dla dodatniej liczby całkowitej n, mającej nieparzysty skrót, wyznacza ten skrót m. Algorytm może operować wyłącznie na liczbach całkowitych i używać tylko podstawowych operacji arytmetycznych (w tym div i mod), porównań, instrukcji sterujących i własnych funkcji — bez funkcji wbudowanych.

Python
def skrot(n):
    m = 0
    p = 1
    while n > 0:
        cyfra = n % 10
        if cyfra % 2 != 0:
            m = m + cyfra * p
            p = p * 10
        n = n // 10
    return m


for n in [294762, 39101]:
    print(n, skrot(n))

Odpowiedź: funkcja skrot (np. skrot(294762) = 97, skrot(39101) = 3911).

↑
PythonC++23Java 25
Treść zadania

Plik skrot.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000, po jednej w wierszu; dla co najmniej jednej z nich nieparzysty skrót (zob. 3.1) nie istnieje.

Napisz program, który poda, dla ilu liczb z pliku nieparzysty skrót nie istnieje, oraz największą z tych liczb. Odpowiedź zapisz w pliku wyniki3_2.txt. Dla pliku skrot_przyklad.txt są dwie takie liczby (266 i 2428), największa to 2428.

Python
def skrot(n):
    m = 0
    p = 1
    while n > 0:
        cyfra = n % 10
        if cyfra % 2 != 0:
            m = m + cyfra * p
            p = p * 10
        n = n // 10
    return m


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

bez_skrotu = [n for n in liczby if skrot(n) == 0]
print(len(bez_skrotu))
print(max(bez_skrotu))

Odpowiedź: 18 liczb, największa z nich: 28422.

↑
PythonC++23Java 25
Treść zadania

Plik skrot2.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000, po jednej w wierszu; każda ma nieparzysty skrót (zob. 3.1).

Napisz program, który wypisze (po jednej w wierszu) te liczby z pliku, dla których największy wspólny dzielnik liczby i jej nieparzystego skrótu jest równy 7. Wynik zapisz w pliku wyniki3_3.txt. Do testów służy plik skrot2_przyklad.txt.

Python
from math import gcd


def skrot(n):
    m = 0
    p = 1
    while n > 0:
        cyfra = n % 10
        if cyfra % 2 != 0:
            m = m + cyfra * p
            p = p * 10
        n = n // 10
    return m


with open("skrot2.txt") as file:
    for wiersz in file:
        n = int(wiersz)
        if gcd(n, skrot(n)) == 7:
            print(n)

Odpowiedź: 784, 14196, 2247, 24087, 3871, 10192.

↑
PythonC++23Java 25
Treść zadania

Plik liczby.txt ma dwa wiersze: w pierwszym jest 3000 liczb pierwszych z przedziału [2, 2000], w drugim — 20 liczb całkowitych z przedziału [2, 1 000 000 000]; liczby oddzielone są spacjami. Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania. Plik liczby_przyklad.txt (200 liczb 2, 3, 5, 7, 31 w pierwszym wierszu i 20 liczb w drugim) służy do testów.

  • 4.1 — Podaj, ile liczb z pierwszego wiersza jest dzielnikiem co najmniej jednej liczby z drugiego wiersza (dla pliku przykładowego: 199).
  • 4.2 — Podaj liczbę, która po uporządkowaniu liczb z pierwszego wiersza jest sto pierwsza, licząc od największej (np. wśród 2, 4, 2, 3, 3, 4 druga od największej to 4; dla pliku przykładowego: 5).
  • 4.3 — Wypisz te liczby z drugiego wiersza, które da się przedstawić jako iloczyn wyłącznie liczb z pierwszego wiersza, przy czym każdy czynnik może wystąpić w iloczynie co najwyżej tyle razy, ile razy występuje w pierwszym wierszu (dla pliku przykładowego: 10 12 14 15 18 20 21 25 27 28; np. 16 = 2·2·2·2 odpada, bo 2 występuje tylko dwa razy).
  • 4.4 — W ciągu liczb z pierwszego wiersza znajdź spójny fragment o co najmniej 50 elementach i największej średniej arytmetycznej (przy remisie — pierwszy w pliku). Podaj tę średnią, liczbę elementów fragmentu i jego pierwszy element (dla pliku przykładowego: 5,52 50 5).
Python
with open("liczby.txt") as file:
    pierwsze = [int(x) for x in file.readline().split()]
    liczby = [int(x) for x in file.readline().split()]

# 4.1
ile = 0
for p in pierwsze:
    for x in liczby:
        if x % p == 0:
            ile += 1
            break
print("4.1", ile)

# 4.2
posortowane = sorted(pierwsze, reverse=True)
print("4.2", posortowane[100])

# 4.3
wystapienia = {}
for p in pierwsze:
    wystapienia[p] = wystapienia.get(p, 0) + 1

wynik = []
for x in liczby:
    reszta = x
    dobra = True
    for p in wystapienia:
        ile_razy = 0
        while reszta % p == 0:
            reszta //= p
            ile_razy += 1
        if ile_razy > wystapienia[p]:
            dobra = False
    if dobra and reszta == 1:
        wynik.append(x)
print("4.3", *wynik)

# 4.4
n = len(pierwsze)
prefiks = [0] * (n + 1)
for i in range(n):
    prefiks[i + 1] = prefiks[i] + pierwsze[i]

najl_suma, najl_dl, najl_start = 0, 1, -1
for start in range(n):
    for koniec in range(start + 50, n + 1):
        suma = prefiks[koniec] - prefiks[start]
        dl = koniec - start
        # suma / dl > najl_suma / najl_dl, bez ułamków
        if najl_start == -1 or suma * najl_dl > najl_suma * dl:
            najl_suma, najl_dl, najl_start = suma, dl, start
print("4.4", najl_suma / najl_dl, najl_dl, pierwsze[najl_start])

Odpowiedź: 4.1: 212. 4.2: 1933. 4.3: 547839600, 2954285, 573219169, 573549984, 212444924. 4.4: średnia 1200,704918… (≈ 1200,70), 61 elementów, pierwszy element 1847.

↑

Edytuj na GitHubie