MINP-R0-100-2405 • Otwarte rozszerzone • 10 pkt • Trudność: ★★★★☆

Zadanie 4

Matura z informatyki, maj 2024, poziom rozszerzony

Wymaganie:

P.I.5) sprawdza poprawność działania algorytmów dla przykładowych danych. P.I.2) stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy: a) na liczbach […]; c) porządkowania ciągu liczb […]. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. II.3) sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów. I+II.2) wykorzystuje znane sobie algorytmy przy rozwiązywaniu i programowaniu rozwiązań następujących problemów: a) rozkładania liczby na czynniki pierwsze, c) znajdowania w ciągu podciągów o różnorodnych własnościach, np. najdłuższego spójnego podciągu niemalejącego, spójnego podciągu o największej sumie.

Treść zadania

Zadanie 4. Liczby

Plik liczby.txt składa się z dwóch wierszy:

pierwszy wiersz pliku zawiera 3000 liczb pierwszych z przedziału [2, 2000]
drugi wiersz pliku zawiera 20 liczb całkowitych z przedziału [2, 1 000 000 000].

Liczby w wierszach są rozdzielone znakami spacji.

Napisz program (lub kilka programów), który(-e) znajdzie(-ą) odpowiedzi do podanych zadań. Każdą odpowiedź zapisz w pliku wyniki4.txt i poprzedź ją numerem oznaczającym zadanie. Do Twojej dyspozycji jest plik liczby_przyklad.txt, który zawiera 200 liczb w pierwszym wierszu (są to wyłącznie liczby 2, 3, 5, 7 i 31) oraz 20 liczb w drugim wierszu. Odpowiedzi dla danych z tego pliku są umieszczone pod każdym zadaniem.

Pamiętaj, że Twój program musi ostatecznie zadziałać na pliku liczby.txt z 3000 liczb w pierwszym wierszu.

Zadanie 4.1. (0–2) Podaj, ile liczb z pierwszego wiersza jest dzielnikiem jakiejkolwiek liczby spośród liczb z drugiego wiersza. Dla pliku liczby_przyklad.txt odpowiedzią jest 199 (tylko liczba 31, która występuje raz, nie jest dzielnikiem żadnej z liczb w drugim wierszu).

Zadanie 4.2. (0–2) Spośród liczb z pierwszego wiersza podaj liczbę, która jest sto pierwszą liczbą w kolejności, licząc od największej po ich uporządkowaniu. Przykład: wśród liczb 2, 4, 2, 3, 3, 4 drugą w kolejności, licząc od największej, jest liczba 4. Dla pliku liczby_przyklad.txt odpowiedzią jest 5.

Zadanie 4.3. (0–3) Dla każdej z liczb z drugiego wiersza rozstrzygnij, czy da się ją przedstawić jako iloczyn jedynie liczb z pierwszego wiersza. Przy tym liczba wystąpień danego czynnika w iloczynie nie może być większa niż liczba wystąpień tego czynnika w pierwszym wierszu. Znajdź wszystkie liczby, które da się tak przedstawić, i je wypisz. Dla pliku liczby_przyklad.txt odpowiedzią są liczby: 10 12 14 15 18 20 21 25 27 28 (liczbę 16 można przedstawić jako iloczyn 2·2·2·2, jednak w pierwszym wierszu liczba 2 występuje tylko dwa razy, więc 16 nie należy do rozwiązania; podobnie jest z liczbą 24 = 2·2·2·3).

Zadanie 4.4. (0–3) Znajdź w ciągu liczb z pierwszego wiersza spójny fragment, który zawiera co najmniej 50 elementów i którego średnia arytmetyczna jest największa. Jeżeli jest więcej niż jeden taki fragment, wybierz ten, który występuje jako pierwszy w pliku liczby.txt. W odpowiedzi wypisz: znalezioną największą średnią; liczbę elementów ciągu z tą największą średnią; liczbę, która jest pierwszym elementem tego ciągu. Dla pliku liczby_przyklad.txt odpowiedzią jest: 5,52 50 5 (największa średnia to 5,52 dla 50 liczb zaczynających się od liczby 5).

Źródło: arkusz CKE MINP-R0-100-2405. Otwórz oryginalny PDF

Rozwiązanie

Odpowiedzi z zasad oceniania CKE:

4.1. 212
4.2. 1933
4.3. 547839600, 2954285, 573219169, 573549984, 212444924
4.4. średnia 1200,704918032787, liczba elementów 61, pierwszy element 1847 (na pozycji 2797)

Wczytanie danych:

with open("liczby.txt") as f:
    lines = f.readlines()
pierwsze = list(map(int, lines[0].split()))   # 3000 liczb pierwszych
drugie   = list(map(int, lines[1].split()))   # 20 liczb całkowitych

4.1. Liczymy te liczby z pierwsze, które dzielą co najmniej jedną liczbę z drugie:

ile = 0
for p in pierwsze:
    if any(d % p == 0 for d in drugie):
        ile += 1
# zapis: "4.1. <ile>"

4.2. Sortujemy pierwszy wiersz malejąco (powtórzenia zostają) i bierzemy element o indeksie 100:

print(sorted(pierwsze, reverse=True)[100])

4.3. Liczby z pierwszego wiersza są pierwsze, więc rozkład na czynniki jest jednoznaczny. Dzielimy d przez kolejne liczby z pierwszego wiersza, ale każdą najwyżej tyle razy, ile razy występuje w tym wierszu; jeśli na końcu zostanie 1, liczba spełnia warunek:

from collections import Counter
ile = Counter(pierwsze)
wynik = []
for d in drugie:
    x = d
    for p, k in ile.items():
        while k > 0 and x % p == 0:
            x //= p
            k -= 1
    if x == 1:
        wynik.append(d)
print(*wynik)

4.4. Sprawdzamy wszystkie fragmenty o długości co najmniej 50 (sumy prefiksowe). Średnie porównujemy dokładnie, na liczbach całkowitych (suma1 · k2 > suma2 · k1), a fragmenty przeglądamy od początku pliku, więc przy remisie zostaje ten, który występuje jako pierwszy:

n = len(pierwsze)
S = [0] * (n + 1)
for i, v in enumerate(pierwsze):
    S[i + 1] = S[i] + v
best_s, best_k, best_i = None, None, None
for i in range(n - 49):
    for k in range(50, n - i + 1):
        s = S[i + k] - S[i]
        if best_s is None or s * best_k > best_s * k:
            best_s, best_k, best_i = s, k, i
print(best_s / best_k, best_k, pierwsze[best_i])

Typowy błąd / pułapka

Uwaga: (1) w 4.1 liczymy liczby z pierwszego wiersza razem z powtórzeniami — liczba pierwsza występująca w wierszu kilka razy liczy się tyle razy, ile występuje (w przykładzie odpowiedź 199 = 200 − 1). Zasady oceniania dają 1 pkt za odpowiedź 2788, czyli liczbę tych, które nie są dzielnikami; (2) w 4.2 liczymy od największej i z powtórzeniami — 1 pkt CKE przyznaje za 31, czyli 101. liczbę od najmniejszej; (3) w 4.3 trzeba uwzględnić krotność wystąpień czynników w pierwszym wierszu — inaczej 16 = 2·2·2·2 błędnie trafi do rozwiązania; (4) w 4.4 przy porównywaniu średnich na liczbach zmiennoprzecinkowych lepiej porównywać iloczyny liczb całkowitych, żeby uniknąć błędów zaokrągleń.

Strona arkusza CKE z treścią zadania

Zadanie 4 - informatyka 2024 PR — Strona arkusza CKE 2024 PR informatyka - zadanie 4 (Liczby). Na podstawie: CKE 2024 Oryginalny PDF CKE, str. 11

Rozwiązanie

Cztery podzadania bazują na tym samym pliku z dwoma wierszami liczb. Wszystkie są problemami pętli i prostych struktur danych — żadnej zaawansowanej algorytmiki.

Kluczowe spostrzeżenia:

4.1 — liczby pierwsze z 1. wiersza mogą się powtarzać; pytanie brzmi “ile liczb”, więc liczymy elementy listy (wraz z powtórzeniami), nie zbiór unikalnych. Każdą liczbę testujemy % p == 0 dla wszystkich 20 liczb z drugiego wiersza.
4.2 — porównujemy ciągi pozycja po pozycji od indeksu 0; przerywamy przy pierwszej różnicy. Wynik = długość wspólnego prefiksu.
4.3 — kombinatorycznie: 1, 2 lub 3 czynniki, z poszanowaniem krotności wystąpień w pierwszym wierszu. Bez ograniczenia krotności rozwiązanie miałoby 16 (jako 2·2·2·2), ale CKE wyklucza tę odpowiedź — to wskazówka, że krotność liczy się.
4.4 — średnia arytmetyczna rośnie z udziałem dużych liczb; dla 3000 liczb pierwszych z [2, 2000] szukamy fragmentu długości ≥ 50 maksymalizującego średnią. Algorytm O(n²) z sumami prefiksowymi mieści się w czasie.

Rozumiesz, jak to rozwiązać?

Przećwicz podobne typy zadań w aplikacji

matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „przetwarzanie pliku tekstowego, dzielniki, kolejność, średnia arytmetyczna” zrobisz samodzielnie.

Otwórz matury-online.pl