Državno natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 3. zadatak - 2. dan

U malom selu Zagvozd otvoren je novi nogometni klub. Poznato je da je nogomet najpopularniji sport u Hrvatskoj i zbog toga su sva djeca odmah pohrlila na upis.

S obzirom na njihove druge obveze djeca su odabrala različite termine treninga koji njima odgovaraju. Svako dijete koje je polaznik nogometnog tečaja odabralo je jedan ili više termina. Svaki termin ima ograničen broj polaznika.

Trener je odabrao neke polaznike, s obzirom na njihove nogometne sposobnosti. Za svakog pojedinog odabranog polaznika odabrao je nekoliko termina koje najbolje odgovaraju tom polazniku.

Potrebne je rasporediti polaznike u termine s time da se zadovolji što je mogude više trenerovih ograničenja uz zadovoljena sva ograničenja polaznika (odnosno da pohađaju jedan od termina koji su naveli kao mogudi) i moraju biti zadovoljena sva ograničenja broja polaznika svakog pojedinog termina.

Ispisati najmanji mogudi broj trenerovih ograničenja koje je potrebno prekršiti da bi postojao raspored koji zadovoljava sva ostala ograničenja.

Napomena: Svako dijete potrebno je dodijeliti u točno jedan termin.

Ukoliko je za nekog polaznika trener odabrao više različitih termina tada smatramo da trenerovo ograničenje nije prekršeno u slučaju da je polaznik dodijeljen u bilo koji od navedenih termina.

ULAZNI PODACI

U prvom retku nalaze se 3 cijela broja: broj N (1 <= N <= 100) – broj polaznik, zatim broj T (1 <= T <= 30) -broj termina, i zatim broj E (1 <= E <= 150)– broj trenerovih ograničenja.

U drugom retku nalaze se brojevi Ci(1<= i <=T) , (1 <= Ci <=N) – maksimalni kapacitet pojedinog termina.

U idudih N redaka nalazi se popis termina koje je odabrao pojedini polaznik:

• prvi broj u retku je cijeli broj Ki (broj termina koje je pojedini polaznik odabrao)
• slijedi Ki brojeva (1 <= Ki <= T) (redni brojevi termina u koje polaznik može pripadati)

Sljededih E redaka predstavlja trenerova ograničenja:

• prvi broj u retku je Ri - redni broj polaznika, (1 <= Ri <= N)
• drugi broj u retku je redni broj termina za kojeg trener smatra da je dobar odabir za pojedinog polaznika.

IZLAZNI PODACI

Jedan broj, minimalni broj trenerovih ograničenja koja je potrebno prekršiti da bi se ostvario navedeni raspored.

PRIMJERI TEST PODATAKA

ulaz

4 3 1
2 2 2
2 1 2
1 3
1 3
2 1 3
1 2

izlaz

0

ulaz

5 3 5
1 1 7
2 1 2
2 1 2
3 1 2 3
2 1 3
1 3
5 3
1 3
4 2
1 1
5 1

izlaz

1

ulaz

10 5 5
1 3 1 1 11
5 1 2 3 4 5
4 2 3 4 5
4 1 2 4 5
5 1 2 3 4 5
3 1 3 5
4 1 2 3 4
4 1 2 4 5
3 1 2 4
3 2 3 5
5 1 2 3 4
4 2
5 3
2 4
4 1
6 3

izlaz

1

Objašnjenje

Objašnjenje za primjer 1:

U selu se nalaze 4 dječaka koji su polaznici. Postoje tri termina za treniranje te je kapacitet svakog od njih jednak 2 polaznika.

Prvi polaznik može pripadati terminima 1 i 2, drugi i tredi polaznik samo terminu 3, dok četvrti polaznik može pripadati terminu 1 i 3.

Trener je postavio samo ograničenje da bi prvom polazniku najbolje odgovarao drugi termin. Ukoliko djecu rasporedimo prema sljededem rasporedu

• 1. polaznik -> 2. termin
• 2 polaznik i 3. polaznik -> 3. termin
• 4 polaznik -> 1. termin

tada su zadovoljena sva ograničenja, stoga je rješenje 0.