Školsko natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) - 3. zadatak

Charcraft je računalna igra u kojoj igrač izgrađuje virtualne svjetove od ASCII znakova te skuplja predmete. Tipovi predmeta su označeni malim slovima engleske abecede, a inventar je niz znakova koji popisuje sve predmete koje igrač posjeduje u nekom trenutku. Redoslijed znakova u inventaru je nebitan — primjerice niz znakova “abba” označava inventar koji se sastoji od dva predmeta tipa “a” te dva predmeta tipa “b”.

Igrač od predmeta u inventaru može izrađivati druge predmete koristeći takozvane recepte — pravila oblika c ← c1c2 . . . ck, gdje su c, c1, c2, . . . , ck sve mala slova engleske abecede. Ovaj recept označava da se jedan predmet tipa c može izraditi od k predmeta čiji su tipovi c1, c2, . . . , ck. Na primjer, recept “d←aabbc” znači da se predmet tipa “d” može izraditi od dva predmeta tipa “a”, dva predmeta tipa “b” te jednog predmeta tipa “c”. Redoslijed znakova s desne strane recepta je nebitan. Naravno, izradom predmeta koristeći neki recept se potroše svi predmeti s desne strane recepta. Primjerice, ako je inventar igrača “aabbcc” onda će nakon izrade predmeta primjenom recepta “d←aabbc” njegov inventar biti “cd”.

Za svaki tip c postoji najviše jedan recept za njegovu izradu. Tip c se ne može pojavljivati s desne strane tog recepta, ali su dozvoljene međuovisnosti (primjerice da se tip c izrađuje pomoću tipa d, a da se tip d izrađuje pomoću tipa c). S desne strane svakog recepta se pojavljuju barem dva znaka, dakle za izradu novog predmeta je uvijek potrebno potrošiti barem dva postojeća predmeta iz inventara.

Zadani je niz recepata te trenutni inventar. Za svaki mogući tip c od “a” do “z” odredite je li moguće da igrač nekako dođe u posjed barem jednog predmeta tog tipa. Naravno, smatramo da je odgovor potvrdan za sve tipove u početnom inventaru igrača.

Ulazni podaci

U prvom redu nalazi se niz od najmanje jednog i najviše 20 malih slova engleske abecede — početni inventar. U drugom redu nalazi se prirodni broj n (n ≤ 26) — broj recepata. U i-tom od sljedećih n redova nalazi se i-ti recept — niz znakova oblika “ci<-si” gdje je ci malo slovo engleske abecede, a si niz od najmanje 2 i najviše 20 malih slova engleske abecede. Između ci i si najprije dolazi znak “<” (manje) pa zatim znak “-” (minus), a razmaci se ne pojavljuju nigdje u receptu. Svi znakovi ci će biti međusobno različiti. U niti jednom se receptu znak ci neće pojavljivati u nizu si .

Izlazni podaci

U prvi red ispišite niz različitih slova engleske abecede (bez razmaka) — tipove za koje je moguće da igrač dođe u njihov posjed. Niz mora biti sortiran uzlazno po abecedi

Bodovanje

• U test podacima vrijednim 30% bodova se u početnom inventaru te s desne strane svakog recepta pojavljuju samo tipovi “a” i “b”

Primjeri test podataka

ulaz

babacc
4
d<-aabbc
e<-abc
f<-de
g<-ee

izlaz

abcdeg

ulaz

aaaaaaaaaa
10
x<-yz
j<-ih
h<-ag
b<-aa
c<-aaa
g<-cd
d<-aaaa
e<-ab
f<-bc
i<-gh

izlaz

abcdefgh

ulaz

mirkoslavko
6
x<-rkorko
y<-koko
t<-mirko
u<-slavko
q<-slavkmirk
w<-slavka

izlaz

aiklmoqrstuvy