{"id":"informatyka-2016-maj-matura-rozszerzona/zad/5.5","paper_id":"informatyka-2016-maj-matura-rozszerzona","number":"5.5","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2016,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 5.1.\n\nBiblioteka planuje wprowadzenie zakazu wypożyczania kilku egzemplarzy tego samego tytułu podręcznika studentom mieszkającym w jednym pokoju. Gdy ta zasada będzie obowiązywać, w żadnym pokoju nie powtórzy się żaden tytuł podręcznika.\n\nPodaj, ile byłoby wypożyczonych podręczników, gdyby takie ograniczenie już funkcjonowało.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**316 podręczników**\n\n## Sposób 1 - analiza problemu\n\n**Reguła:** w jednym pokoju nie może być więcej niż jeden egzemplarz tego samego tytułu. Czyli z każdej trójki `(pokój, tytuł)` zliczamy 1 wypożyczenie (zamiast np. 2-3, gdy 2-3 osób z tego samego pokoju wypożyczyło ten sam podręcznik).\n\n**Studenci SPOZA miasteczka nie mają pokoju** → ich wypożyczenia liczymy WSZYSTKIE (każdy student spoza to \"osobny pokój\").\n\n**Algorytm:**\n1. Dla studentów Z miasteczka: zlicz **unikalne pary (id_pok, tytul)**.\n2. Dla studentów SPOZA miasteczka: zlicz wszystkie ich wypożyczenia.\n3. Suma = wynik.\n\n## Sposób 2 - SQL\n\n```sql\nSELECT\n(\n-- studenci z miasteczka: unikalne pary (pokój, tytuł)\nSELECT COUNT(DISTINCT m.id_pok || '|' || w.tytul)\nFROM wypozyczenia w\nJOIN meldunek m ON w.pesel = m.pesel\n)\n(\n-- studenci spoza miasteczka: wszystkie wypożyczenia\nSELECT COUNT(*)\nFROM wypozyczenia w\nWHERE w.pesel NOT IN (SELECT pesel FROM meldunek)\n) AS razem;\n\n**Alternatywnie - z UNION:**\n```sql\nSELECT COUNT(*) FROM (\nSELECT DISTINCT m.id_pok, w.tytul\nFROM wypozyczenia w\nJOIN meldunek m ON w.pesel = m.pesel\nUNION ALL\nSELECT NULL, w.tytul\nFROM wypozyczenia w\nWHERE w.pesel NOT IN (SELECT pesel FROM meldunek)\n) AS unique_loans;\n\n## Sposób 3 - Python\n\n```python\n# Wczytaj meldunek: pesel -> id_pok\nmeldunek = {}\nwith open('meldunek.txt', encoding='windows-1250') as f:\nnext(f)\nfor linia in f:\ncz = linia.strip().split('\\t')\nif len(cz) >= 2:\nmeldunek[cz[0]] = cz[1]\n\n# Wczytaj wypożyczenia\nwypozyczenia_z_kampusu = set() # zbiór par (id_pok, tytul)\nwypozyczenia_spoza = 0\nwith open('wypozyczenia.txt', encoding='windows-1250') as f:\nnext(f)\nfor linia in f:\ncz = linia.strip().split('\\t')\nif len(cz) >= 3:\npesel, tytul = cz[1], cz[2]\nif pesel in meldunek:\nwypozyczenia_z_kampusu.add((meldunek[pesel], tytul))\nelse:\nwypozyczenia_spoza += 1\n\nrazem = len(wypozyczenia_z_kampusu) + wypozyczenia_spoza\nprint(razem) # 316\n\n## Sposób 4 - arkusz kalkulacyjny\n\n1. Wypożyczenia: dodaj kolumnę D z `=WYSZUKAJ.PIONOWO(B2; meldunek!A:B; 2; FAŁSZ)` (zwraca id_pok lub błąd dla SPOZA).\n2. Dodaj kolumnę E z formułą: `=JEŻELI(JEST.BŁĄD(D2); C2&\"|SPOZA|\"&A2; D2&\"|\"&C2)` - unikalny klucz dla każdego wiersza.\n- Dla SPOZA klucz zawiera nr wypożyczenia (zawsze unikatowy).\n- Dla z miasteczka klucz = id_pok + tytul (powtórki w pokoju mają ten sam klucz).\n3. Liczba unikalnych: `=ILE.NIEPUSTYCH.UNIKATOWYCH(E2:E_end)` → 316.\n\n## Reference informatyczny - DISTINCT + grupowanie\n\n> Reference - `COUNT(DISTINCT )`:\n> - Liczy liczbę **unikalnych** wartości w wyrażeniu.\n> - W większości SQL można konkatenować pola: `COUNT(DISTINCT a || '|' || b)` lub `COUNT(DISTINCT (a, b))` w PostgreSQL.\n> - **Pułapka NULL**: `COUNT(DISTINCT)` ignoruje NULLe.\n>\n> Reference - Pythonowy zbiór `set` z tuple:\n> - `s.add((a, b))` - dodaje krotkę; ZBIÓR przechowuje tylko unikalne.\n> - `len(s)` - liczba unikalnych krotek.\n> - **Wydajność**: O(1) amortyzowane na operację.\n>\n> Reference - Sprytna alternatywa:\n> - Zamiast `(id_pok, tytul)`, klucz dla SPOZA = `(pesel, tytul)` (unikalny per student) - wtedy nie trzeba rozdzielać przypadków.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 5.5, max 3 pkt):\n> - **3 pkt** - prawidłowy wynik **316**\n> - **1 pkt** - wynik NIEUWZGLĘDNIAJĄCY studentów spoza kampusu (311)\n> - **0 pkt** - błędna albo brak\n>\n> **Uwaga: NIE PRZYZNAJE SIĘ 2 PUNKTÓW.**\n\n## Typowe pułapki\n\n- **Pominięcie studentów spoza miasteczka** - wynik 311 zamiast 316 (różnica = 5 osób z 5.4, każda z co najmniej 1 wypożyczeniem). **Krytyczne!**\n- **Liczenie tylko `COUNT(*)` na pierwszym JOIN** - to da pełną liczbę wypożyczeń z kampusu, bez deduplikacji.\n- **Pomyłka z dopuszczalną redundancją** - niektórzy uczniowie odejmują wypożyczenia, zamiast policzyć unikalne pary.\n- **Pomylenie pokoju z PESEL** - pokój identyfikuje grupę współlokatorów, NIE jedną osobę.\n- **Sortowanie niepotrzebne** - zadanie pyta o LICZBĘ, nie listę.\n\n## Złożoność obliczeniowa\n\n- Wczytanie meldunek: O(M).\n- Wczytanie wypożyczeń: O(W).\n- Set z parami: O(W) operacji amortyzowanych.\n- **Łącznie: O(M + W).**","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2016 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 5.1.

\n

Biblioteka planuje wprowadzenie zakazu wypożyczania kilku egzemplarzy tego samego tytułu podręcznika studentom mieszkającym w jednym pokoju. Gdy ta zasada będzie obowiązywać, w żadnym pokoju nie powtórzy się żaden tytuł podręcznika.

\n

Podaj, ile byłoby wypożyczonych podręczników, gdyby takie ograniczenie już funkcjonowało.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

316 podręczników

\n

Sposób 1 - analiza problemu

\n

Reguła: w jednym pokoju nie może być więcej niż jeden egzemplarz tego samego tytułu. Czyli z każdej trójki (pokój, tytuł) zliczamy 1 wypożyczenie (zamiast np. 2-3, gdy 2-3 osób z tego samego pokoju wypożyczyło ten sam podręcznik).

\n

Studenci SPOZA miasteczka nie mają pokoju → ich wypożyczenia liczymy WSZYSTKIE (każdy student spoza to "osobny pokój").

\n

Algorytm:

\n
  1. Dla studentów Z miasteczka: zlicz unikalne pary (id_pok, tytul).
  2. Dla studentów SPOZA miasteczka: zlicz wszystkie ich wypożyczenia.
  3. Suma = wynik.
\n

Sposób 2 - SQL

\n

```sql
SELECT
(
-- studenci z miasteczka: unikalne pary (pokój, tytuł)
SELECT COUNT(DISTINCT m.id_pok || '|' || w.tytul)
FROM wypozyczenia w
JOIN meldunek m ON w.pesel = m.pesel
)
(
-- studenci spoza miasteczka: wszystkie wypożyczenia
SELECT COUNT(*)
FROM wypozyczenia w
WHERE w.pesel NOT IN (SELECT pesel FROM meldunek)
) AS razem;

\n

Alternatywnie - z UNION:
```sql
SELECT COUNT(*) FROM (
SELECT DISTINCT m.id_pok, w.tytul
FROM wypozyczenia w
JOIN meldunek m ON w.pesel = m.pesel
UNION ALL
SELECT NULL, w.tytul
FROM wypozyczenia w
WHERE w.pesel NOT IN (SELECT pesel FROM meldunek)
) AS unique_loans;

\n

Sposób 3 - Python

\n

```python

\n

Wczytaj meldunek: pesel -> id_pok

\n

meldunek = {}
with open('meldunek.txt', encoding='windows-1250') as f:
next(f)
for linia in f:
cz = linia.strip().split('\\t')
if len(cz) >= 2:
meldunek[cz[0]] = cz[1]

\n

Wczytaj wypożyczenia

\n

wypozyczenia_z_kampusu = set() # zbiór par (id_pok, tytul)
wypozyczenia_spoza = 0
with open('wypozyczenia.txt', encoding='windows-1250') as f:
next(f)
for linia in f:
cz = linia.strip().split('\\t')
if len(cz) >= 3:
pesel, tytul = cz[1], cz[2]
if pesel in meldunek:
wypozyczenia_z_kampusu.add((meldunek[pesel], tytul))
else:
wypozyczenia_spoza += 1

\n

razem = len(wypozyczenia_z_kampusu) + wypozyczenia_spoza
print(razem) # 316

\n

Sposób 4 - arkusz kalkulacyjny

\n
  1. Wypożyczenia: dodaj kolumnę D z =WYSZUKAJ.PIONOWO(B2; meldunek!A:B; 2; FAŁSZ) (zwraca id_pok lub błąd dla SPOZA).
  2. Dodaj kolumnę E z formułą: =JEŻELI(JEST.BŁĄD(D2); C2&"|SPOZA|"&A2; D2&"|"&C2) - unikalny klucz dla każdego wiersza.
\n\n
  1. Liczba unikalnych: =ILE.NIEPUSTYCH.UNIKATOWYCH(E2:E_end) → 316.
\n

Reference informatyczny - DISTINCT + grupowanie

\n
Reference - COUNT(DISTINCT ):
- Liczy liczbę unikalnych wartości w wyrażeniu.
- W większości SQL można konkatenować pola: COUNT(DISTINCT a || '|' || b) lub COUNT(DISTINCT (a, b)) w PostgreSQL.
- Pułapka NULL: COUNT(DISTINCT) ignoruje NULLe.

Reference - Pythonowy zbiór set z tuple:
- s.add((a, b)) - dodaje krotkę; ZBIÓR przechowuje tylko unikalne.
- len(s) - liczba unikalnych krotek.
- Wydajność: O(1) amortyzowane na operację.

Reference - Sprytna alternatywa:
- Zamiast (id_pok, tytul), klucz dla SPOZA = (pesel, tytul) (unikalny per student) - wtedy nie trzeba rozdzielać przypadków.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 5.5, max 3 pkt):
- 3 pkt - prawidłowy wynik 316
- 1 pkt - wynik NIEUWZGLĘDNIAJĄCY studentów spoza kampusu (311)
- 0 pkt - błędna albo brak

Uwaga: NIE PRZYZNAJE SIĘ 2 PUNKTÓW.
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}