Matura informatyka

Matura 2015 — maj, poziom rozszerzony (stara formuła)

PythonC++23Java 25
Treść zadania

Potęgi dwójki. Każdą dodatnią liczbę całkowitą n można zapisać jako sumę różnych potęg liczby 2, np. 11 = 1 + 2 + 8 = 2⁰ + 2¹ + 2³, 18 = 2 + 16 = 2¹ + 2⁴.

Zapisz liczby 23 i 50 jako sumy różnych potęg liczby 2 (dla 11 odpowiedzią jest 1 + 2 + 8).

Python
def skladniki(n):
    wynik = []
    potega = 1
    while n > 0:
        if n % 2 == 1:
            wynik.append(potega)
        n = n // 2
        potega *= 2
    return wynik


for n in [11, 23, 50]:
    print(n, "=", " + ".join(str(x) for x in skladniki(n)))

Odpowiedź: 23 = 1 + 2 + 4 + 16, 50 = 2 + 16 + 32

↑
PythonC++23Java 25
Treść zadania

Każdą dodatnią liczbę całkowitą n można zapisać jako sumę różnych potęg liczby 2. Zapisz algorytm (lista kroków, schemat blokowy lub język programowania), który oblicza, ile różnych potęg dwójki daje w sumie n. Można używać dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia lub własnych funkcji.

Specyfikacja — dane: n — dodatnia liczba całkowita; wynik: lp — liczba różnych potęg dwójki, których suma wynosi n.

Przykład: dla n = 18 wynikiem jest lp = 2.

Python
def liczba_poteg(n):
    lp = 0
    while n > 0:
        lp += n % 2
        n = n // 2
    return lp


print(liczba_poteg(18))

Odpowiedź: dla n = 18 wynik lp = 2 (liczba jedynek w zapisie binarnym n)

↑
PythonC++23Java 25
Treść zadania

Koszyk zabawek. Wygrałeś koszyk zakupów o łącznej masie co najwyżej 10 kg i chcesz, by wartość zabawek była jak największa. Dostępne zabawki (masa, cena): rowerek 8 kg, 320 zł; wózek dla lalek 4 kg, 152 zł; lalka 1 kg, 37 zł; duży miś 2 kg, 70 zł; klocki 3 kg, 99 zł; hulajnoga 5 kg, 155 zł; mały miś 1 kg, 30 zł. Strategie wyboru (zawsze pilnując limitu masy):

  • I — od najdroższej do najtańszej (przy równej cenie lżejsza),
  • II — od najlżejszej do najcięższej (przy równej masie droższa),
  • III — od największego do najmniejszego ilorazu cena/masa.

Przy kilku zabawkach spełniających kryterium wybierasz dowolną.

  • 2.1 — Zakładając, że te same zabawki można brać wielokrotnie, podaj dla każdej strategii I, II, III zawartość koszyka (nazwy i liczby egzemplarzy) oraz jego łączną wartość.
  • 2.2 — Uzupełnij brakujące kroki 2 i 7 algorytmu obliczającego wartość koszyka dla strategii III (zabawki mogą się powtarzać). Dane: mk — limit masy, n — liczba artykułów, MASA[1..n], CENA[1..n] — masy i ceny uporządkowane nierosnąco według ilorazu cena/masa (wszystko dodatnie całkowite). Wynik: K[1..n] — liczby egzemplarzy kolejnych zabawek w koszyku, w — łączna wartość koszyka.
Kod
krok 1: dla i = 1 do n wykonaj K[i] ← 0
krok 2: ............
krok 3: i ← 1
krok 4: dopóki i <= n oraz mk > 0
krok 5:     K[i] ← mk div MASA[i]
krok 6:     mk ← mk mod MASA[i]
krok 7:     ............
krok 8:     i ← i + 1
Python · zabawki: (nazwa, masa, cena)
zabawki = [("rowerek", 8, 320), ("wozek dla lalek", 4, 152), ("lalka", 1, 37), ("duzy mis", 2, 70),
           ("klocki", 3, 99), ("hulajnoga", 5, 155), ("maly mis", 1, 30)]


def koszyk_z_powtorzeniami(lista, mk):
    # algorytm z zadania 2.2 - zachlannie, kazda zabawka moze wystapic wiele razy
    K = [0] * len(lista)
    w = 0                              # krok 2
    i = 0
    while i < len(lista) and mk > 0:
        nazwa, masa, cena = lista[i]
        K[i] = mk // masa
        mk = mk % masa
        w = w + K[i] * cena            # krok 7
        i += 1
    return K, w


strategie = {
    "I": sorted(zabawki, key=lambda z: (-z[2], z[1])),     # od najdrozszej, przy remisie lzejsza
    "II": sorted(zabawki, key=lambda z: (z[1], -z[2])),    # od najlzejszej, przy remisie drozsza
    "III": sorted(zabawki, key=lambda z: -z[2] / z[1]),    # od najwiekszego ilorazu cena/masa
}

for nazwa_strategii, lista in strategie.items():
    K, w = koszyk_z_powtorzeniami(lista, 10)
    zawartosc = [f"{K[i]}x {lista[i][0]}" for i in range(len(lista)) if K[i] > 0]
    print(nazwa_strategii, zawartosc, w)

Odpowiedź: I: rowerek + duży miś, 390 zł; II: 10x lalka, 370 zł; III: rowerek + 2x lalka, 394 zł. Uzupełnienie algorytmu: krok 2: w ← 0, krok 7: w ← w + K[i] * CENA[i]

↑
PythonC++23Java 25
Treść zadania

Koszyk zabawek o limicie 10 kg i zabawki jak w zadaniu 2.1 (rowerek 8 kg/320 zł, wózek 4 kg/152 zł, lalka 1 kg/37 zł, duży miś 2 kg/70 zł, klocki 3 kg/99 zł, hulajnoga 5 kg/155 zł, mały miś 1 kg/30 zł); strategie I (od najdroższej), II (od najlżejszej), III (od największego ilorazu cena/masa).

  • 2.3 — Zakładając, że zabawki nie mogą się powtarzać, podaj dla każdej strategii I, II, III nazwy wybranych zabawek i łączną wartość koszyka.
  • 2.4 — Zapisz algorytm doboru zabawek według strategii III bez powtórzeń. Dane: mk, n, MASA[1..n], CENA[1..n] (uporządkowane nierosnąco według ilorazu cena/masa). Wynik: K[1..n], gdzie K[i] = 1, gdy i-ta zabawka trafiła do koszyka, a 0 w przeciwnym razie, oraz w — łączna wartość koszyka.
Python
zabawki = [("rowerek", 8, 320), ("wozek dla lalek", 4, 152), ("lalka", 1, 37), ("duzy mis", 2, 70),
           ("klocki", 3, 99), ("hulajnoga", 5, 155), ("maly mis", 1, 30)]


def koszyk_bez_powtorzen(lista, mk):
    # algorytm z zadania 2.4 - kazda zabawka co najwyzej raz
    K = [0] * len(lista)
    w = 0
    for i in range(len(lista)):
        nazwa, masa, cena = lista[i]
        if masa <= mk:
            K[i] = 1
            mk -= masa
            w += cena
    return K, w


strategie = {
    "I": sorted(zabawki, key=lambda z: (-z[2], z[1])),
    "II": sorted(zabawki, key=lambda z: (z[1], -z[2])),
    "III": sorted(zabawki, key=lambda z: -z[2] / z[1]),
}

for nazwa_strategii, lista in strategie.items():
    K, w = koszyk_bez_powtorzen(lista, 10)
    zawartosc = [lista[i][0] for i in range(len(lista)) if K[i] == 1]
    print(nazwa_strategii, zawartosc, w)

Odpowiedź: I: rowerek, duży miś — 390 zł; II: lalka, mały miś, duży miś, klocki — 236 zł; III: rowerek, lalka, mały miś — 387 zł

↑
PythonC++23Java 25
Treść zadania

W pliku slowa.txt jest 1000 słów zerojedynkowych o długości od 2 do 25 znaków, po jednym w wierszu. Odpowiedzi zapisz w pliku wynik4.txt, poprzedzając każdą numerem zadania. Blokiem nazywamy maksymalny (niedający się wydłużyć) ciąg kolejnych jednakowych znaków — np. słowo 100110001 ma 5 bloków: 1, 00, 11, 000, 1.

Podaj, ile słów z pliku ma więcej zer niż jedynek.

Przykład: dla słów 101011010011001100111, 10001001, 0001000, 101010011100, 000011, 1111100 wynikiem jest 3.

Python
licznik = 0

with open("slowa.txt") as file:
    for line in file:
        slowo = line.strip()
        if slowo.count("0") > slowo.count("1"):
            licznik += 1

print(licznik)

Odpowiedź: 441

↑
PythonC++23Java 25
Treść zadania

Plik slowa.txt zawiera 1000 słów zerojedynkowych. Podaj, ile słów składa się z dokładnie dwóch niepustych bloków: pierwszego złożonego z samych zer i drugiego — z samych jedynek (czyli postaci 0…01…1). Odpowiedź zapisz w wynik4.txt.

Przykład: dla słów 100010000100, 000000111111, 00000000, 11111111110000, 00000000000000001 wynikiem jest 2.

Python
licznik = 0

with open("slowa.txt") as file:
    for line in file:
        slowo = line.strip()
        # dokladnie dwa bloki: najpierw same zera, potem same jedynki
        zera = len(slowo) - len(slowo.lstrip("0"))
        if 0 < zera < len(slowo) and slowo[zera:] == "1" * (len(slowo) - zera):
            licznik += 1

print(licznik)

Odpowiedź: 44

↑
PythonC++23Java 25
Treść zadania

Plik slowa.txt zawiera 1000 słów zerojedynkowych. Podaj długość najdłuższego bloku złożonego z samych zer, występującego w słowach z pliku, i wypisz wszystkie słowa zawierające blok zer o tej długości. Odpowiedź zapisz w wynik4.txt.

Przykład: dla słów 100010000100, 001, 000, 10101001110000, 000011 wynikiem jest 4 oraz słowa 100010000100, 10101001110000 i 000011.

Python
def najdluzszy_blok_zer(slowo):
    najdluzszy = biezacy = 0
    for znak in slowo:
        if znak == "0":
            biezacy += 1
            najdluzszy = max(najdluzszy, biezacy)
        else:
            biezacy = 0
    return najdluzszy


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

maks = 0
for slowo in slowa:
    maks = max(maks, najdluzszy_blok_zer(slowo))

print(maks)
for slowo in slowa:
    if najdluzszy_blok_zer(slowo) == maks:
        print(slowo)

Odpowiedź: 10; 001010000000000, 1001010001000000000011001

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Ogródki działkowe: 100 działek po 500 m². Plik deszcz.txt zawiera dla dni od 1 maja do 30 września 2014 roku datę i liczbę 0 (brak opadów) lub 1 (deszcz), rozdzielone tabulatorem (pierwszy wiersz to nagłówek data opady). Zbiornik na deszczówkę ma pojemność 2 500 000 litrów; w nocy z 30 kwietnia na 1 maja był pełny. Zasady:

  • w dzień bez deszczu rano zrasza się działki (2 litry na 1 m²), a wieczorem z pozostałej wody ubywa 1% przez parowanie,
  • w dzień deszczowy zraszacze nie działają, a wieczorem woda w zbiorniku zwiększa się o 3% względem stanu z rana; nadmiar ponad pojemność trafia do kanalizacji,
  • na koniec każdej soboty wodociągi dolewają wodę — maksymalnie 500 000 litrów, nie przekraczając pojemności zbiornika.

Obliczenia prowadź bez zaokrągleń, odpowiedzi podaj zaokrąglone do liczb całkowitych. Wskazówka: 1 czerwca 2014 rano w zbiorniku było ok. 2 336 406 litrów. Odpowiedzi zapisz w pliku wynik6.txt.

  • 6.1 — W ilu dniach w badanym okresie deszczówka będzie odprowadzana do kanalizacji?
  • 6.2 — Ile łącznie wody pobrano z wodociągów na uzupełnianie zbiornika?
  • 6.3 — Którego dnia rano w zbiorniku będzie najmniej wody? Podaj datę i ilość wody.
  • 6.4 — Dla każdej majowej soboty podaj jej datę, ilość wody odprowadzonej tego dnia do kanalizacji i ilość wody dolanej z wodociągów.
  • (6.5 — narysuj wykres kolumnowy ilości dolewanej wody w sobotach maja.)
Python
from datetime import date

POJEMNOSC = 2500000
woda = POJEMNOSC
dni_odprowadzania = 0
z_wodociagow = 0
najmniej = None
soboty_maja = []

with open("deszcz.txt") as file:
    next(file)
    for line in file:
        data, opady = line.split()
        dzien = date.fromisoformat(data)
        # stan rano
        if najmniej is None or woda < najmniej[1]:
            najmniej = (data, woda)
        odprowadzono = 0
        if opady == "1":
            woda *= 1.03
            if woda > POJEMNOSC:
                odprowadzono = woda - POJEMNOSC
                woda = POJEMNOSC
                dni_odprowadzania += 1
        else:
            woda -= 100 * 500 * 2      # zraszanie 100 dzialek po 500 m2, 2 l/m2
            woda *= 0.99               # parowanie
        dolano = 0
        if dzien.weekday() == 5:       # sobota
            dolano = min(500000, POJEMNOSC - woda)
            woda += dolano
            z_wodociagow += dolano
            if dzien.month == 5:
                soboty_maja.append((data, round(odprowadzono), round(dolano)))

print("6.1", dni_odprowadzania)
print("6.2", round(z_wodociagow))
print("6.3", najmniej[0], round(najmniej[1]))
print("6.4")
for wiersz in soboty_maja:
    print(*wiersz)

Odpowiedź: 6.1: 13; 6.2: 8 289 356 (lub 8 289 355); 6.3: 2014-09-20, 1 303 938 l; 6.4: 2014-05-03 0 176 193, 2014-05-10 75 000 0, 2014-05-17 0 109 538, 2014-05-24 0 354 118, 2014-05-31 0 500 000; 6.5 — wykres kolumnowy z kolumny „dolano” zestawienia 6.4

↑

Edytuj na GitHubie