Županijsko natjecanje iz informatike 2020. / Druga podskupina (3. i 4. razred) - 3. zadatak

Albert Einstein bio je vrhunski znanstvenik, no manje je poznato da je obožavao i logičke slagalice.

Integram, jedna vrsta logičke slagalice, često se naziva upravo njegovim imenom, Einsteinovom zagonetkom. Primjer jednog integrama dan je u nastavku:

Marko, Darko, Vlatka i Zlatka idu u istu srednju školu, ali međusobno različite razrede.

Svatko od njih posjeduje jednog kućnog ljubimca: psa, mačku, kornjaču ili papigu.

Otkrijte tko ide u koji razred te koje ljubimce posjeduju, ako je poznato da:

1. Marko ide u prvi razred.
2. Vlatka ima psa.
3. U četvrti razred ide Zlatka.
4. Kornjača nije Markov kućni ljubimac.
5. Učenik/ica trećeg razreda ima mačku.
6. Vlatka nema papigu.
7. Zlatka nema papigu.

Integram se sastoji od k kategorija. Na gornjem primjeru to su ime, razred i kućni ljubimac.

Svaka kategorija sastoji se od n različitih elemenata.

Primjerice, u kategoriji ime nalaze se elementi Marko, Darko, Vlatka i Zlatka, u kategoriji kućni ljubimac nalaze se pas, mačka, kornjača i papiga, dok se kategorija razred odnosi na elemente prvog, drugog, trećeg i četvrtog razreda.

U integramu pretpostavljamo da postoji n subjekata od kojih svaki ima po jedan element svake kategorije (različit od drugih subjekata).

Cilj slagalice je povezati elemente iz različitih kategorija koristeći skup od m spoznaja (na primjeru označenih brojevima od 1 do 7).

Nedavno je na hrvatskom enigmatskom portalu objavljen novi integram. Sve spoznaje zadane su u jednom od sljedećih dvaju oblika:

• element1 je element2 – ova spoznaja predstavlja povezanost dvaju elemenata različitih kategorija, tj. da element1 i element2 pripadaju istom subjektu. Na primjer, prva spoznaja iz gornjeg primjera u ovom obliku glasila bi marko je prvi.

• element1 nije element2 – ova spoznaja govori da dva elementa različitih kategorija nisu povezana, tj. da ne pripadaju istom subjektu. Primjerice, četvrta spoznaja iz gornjeg primjera u ovom bi obliku glasila kornjaca nije marko.

Vaš je zadatak da za zadani integram otkrijete što više novih spoznaja, koje se ispituju kroz q provjera.

Svaka provjera ima oblik ’element kategorija’: za subjekta koji u nekoj kategoriji ima element element treba odrediti oznaku elementa u (drugoj) kategoriji kategorija.

Primjerice, ako bi nas za gornji primjer zanimalo koji je Darkov kućni ljubimac, oblik provjere bio bi ’darko ljubimac’.

Pritom je moguće da su autori integrama bili nepažljivi te da nije moguće jednoznačno odrediti o kojem je elementu riječ.

Ipak, možete pretpostaviti da je skup zadanih spoznaja konzistentan, tj. da nema proturječnih spoznaja.

Ulazni podaci

U prvom su retku prirodni brojevi k (2 ≤ k ≤ 5) i n (2 ≤ n ≤ 4), broj kategorija i broj elemenata u svakoj kategoriji.

Svaki od sljedećih k redaka sadrži n + 1 riječi koje opisuju pojedinu kategoriju.

Prva riječ u retku predstavlja oznaku kategorije, a preostalih n riječi oznake elemenata u toj kategoriji.

U sljedećem je retku prirodan broj m (1 ≤ m ≤ 20), broj zadanih spoznaja.

U svakom od sljedećih m redaka nalazi se po jedna spoznaja u jednom od sljedećih dvaju oblika: element1 je element2 ili element1 nije element2. Zadani elementi bit će iz različitih kategorija.

U sljedećem je retku prirodan broj q (2 ≤ q ≤ 100), broj provjera.

U svakom u sljedećih q redaka nalazi se po jedna provjera u obliku element kategorija, pri čemu element ne pripada kategoriji kategorija.

Sve riječi u ulazu sastojat će se od malih slova engleske abecede te neće biti dulje od 10 znakova.

Oznake svih elemenata (u svim kategorijama) bit će međusobno različite.

Izlazni podaci

Potrebno je ispisati q redaka. Za svaku provjeru ispišite njezino rješenje. Ako rješenje nije moguće jednoznačno odrediti, ispišite broj -1.

Primjer zadatka

Ulaz

2 3
grad zagreb bec prag
drzava austrija hrvatska ceska
2
prag je ceska
austrija je bec
2
ceska grad
zagreb drzava

Izlaz

prag
hrvatska

Objašnjenje

U prvom probnom primjeru poznato je da element prag pripada elementu ceska te da element austrija

pripada elementu bec. Dakle, eliminacijom možemo zaključiti da su elementi hrvatska i zagreb povezani.

Ulaz

5 2
voce jabuka kruska
ime mirko slavko
sport plivanje skakanje
zanimanje student profesor
prijevoz autobus vlak
3
mirko je jabuka
slavko nije plivanje
student je vlak
3
profesor prijevoz
slavko voce
slavko zanimanje

Izlaz

autobus
kruska
-1

Objašnjenje

U drugom probnom primjeru zadano je da su elementi vlak i student povezani.

Prema tome, može se zaključiti da su povezani i elementi profesor i autobus.

Na sličan način dolazimo do zaključka da element kruska pripada elementu slavko.

Međutim, nema dovoljno informacija da se odredi koje je zanimanje

povezano s elementom slavko.

Ulaz

3 4
ime mirko slavko marko darko
grad zagreb rijeka split osijek
zanimanje pjevac plesac glumac programer
5
mirko je rijeka
mirko nije programer
rijeka nije plesac
slavko je pjevac
darko nije glumac
5
mirko zanimanje
darko zanimanje
darko grad
slavko zanimanje
glumac grad

Izlaz

glumac
-1
-1
pjevac
rijeka