Zadanie 3.2. (0-3)
Wspólną liczbę wystąpień litery x w słowach s1, s2 oznaczymy przez W(x, s1, s2) i definiujemy
jako
W(x, s1, s2) = minimum(d(x, s1), d(x, s2))
gdzie d(x, s) oznacza liczbę wystąpień litery x w słowie s.
Podaj parę słów występujących w jednym wierszu w pliku pary.txt, dla której suma
wspólnych wystąpień wszystkich liter jest największa, oraz podaj tę sumę. Jest jedna taka
para.
3.1.
0-1-2
3.2.
0-1-
2-3
MINP-R0_100
Przykład:
Dla poniższej pary słów wypisano wspólną liczbę wystąpień wszystkich liter (wyniki wypisano
w kolejności alfabetycznej):
adabbcdde aadabbbccdc → a: 2, b: 2, c: 1, d: 2, e: 0
Suma wspólnych wystąpień wszystkich liter dla pary z tego przykładu wynosi:
2 + 2 + 1 + 2 = 7.
Dla pliku pary_przyklad.txt poprawną odpowiedzią jest
ccccdcedddddecde ccdcdddecc 10
Zadanie 3.2. (0-3)
Wymaganie ogólne
Wymagania szczegółowe
II. Programowanie i rozwiązywanie
problemów z wykorzystaniem komputera
oraz innych urządzeń cyfrowych: układanie
i programowanie algorytmów,
organizowanie, wyszukiwanie
i udostępnianie informacji, posługiwanie się
aplikacjami komputerowymi.
Zdający:
P.II.1) projektuje i programuje rozwiązania
problemów z różnych dziedzin, stosuje przy
tym: instrukcje wejścia/wyjścia, wyrażenia
arytmetyczne i logiczne, instrukcje
warunkowe, instrukcje iteracyjne, funkcje
z parametrami i bez parametrów, testuje
poprawność programów dla różnych
danych; w szczególności programuje
algorytmy z punktu I.2).
II.1) projektuje i tworzy rozbudowane
programy w procesie rozwiązywania
problemów, wykorzystuje w programach
dobrane do algorytmów struktury danych,
w tym struktury dynamiczne i korzysta
z dostępnych bibliotek dla tych struktur.
II.2) sprawnie posługuje się zintegrowanym
środowiskiem programistycznym przy
pisaniu, uruchamianiu i testowaniu
programów.
Zasady oceniania
3 pkt - odpowiedź poprawna, w tym:
2 pkt - para słów
1 pkt - liczba.
0 pkt - odpowiedź niepoprawna albo brak odpowiedzi.
Poprawna odpowiedź
aacbcccaacacbcabac cccccaaaacaccbabcba 18
aacbcccaacacbcabac cccccaaaacaccbabcba — suma 18
Para: aacbcccaacacbcabac cccccaaaacaccbabcba, suma wspólnych wystąpień = 18.
Dla pary słów $s_1, s_2$ i każdej litery $x$ liczymy $d(x,s_1)$ i $d(x,s_2)$ (liczby wystąpień) oraz
$$W(x,s_1,s_2)=\\min\\big(d(x,s_1),\\,d(x,s_2)\\big).$$
Suma wspólnych wystąpień to $\\sum_x W(x,s_1,s_2)$ - czyli tzw. przekrój wielozbiorów liter. Szukamy pary o największej takiej sumie.
Algorytm (dla każdego wiersza; wygodnie użyć Counter):
```python
from collections import Counter
naj = -1; para = ('', '')
with open('pary.txt') as f:
for line in f:
s1, s2 = line.split()
c1, c2 = Counter(s1), Counter(s2)
suma = sum(min(c1[x], c2[x]) for x in set(c1) & set(c2))
if suma > naj:
naj = suma; para = (s1, s2)
print(para[0], para[1], naj)
Wysoka suma wspólnych wystąpień występuje, gdy oba słowa są długie i zbudowane z tego samego, wąskiego zestawu liter (tu głównie a, b, c). Dla podanej pary oba słowa mają po 18 znaków złożonych niemal wyłącznie z a, b, c, przez co minima wystąpień dla poszczególnych liter sumują się do maksymalnej wartości:
$$\\sum_x W(x,s_1,s_2) = \\mathbf{18}.$$
Odpowiedź zapisujemy w wyniki3.txt, poprzedzając ją numerem zadania.
(Uwaga: brak konkretnej odpowiedzi ze strony AI jest rozbieżny z kluczem - wymagana jest wskazana para i suma 18.)
"}]}