Školska razina 2019 / Osnovna škola (8. razred) - zadatak 3

Mirko je stalni sudionik festivala barokne glazbe. Ove godine nije pozvan jer se prošle posvađao s organizatorima oko toga treba li na festivalu izvoditi Bachove i Händelove skladbe u moderniziranoj verziji na harmonici. Nasreću, Mirko ima plan kako ući na festival nepozvan.

Svake godine za ulazak na festival potrebno je imati oko ruke zavezanu narukvicu na kojoj je napisan određeni kod. Narukvicu možemo zamisliti kao papirnatu traku s napisanim nizom slova (kodom) pri čemu je početak trake zalijepljen na njezin kraj tako da se slova ne preklapaju te se nalaze na vanjskoj strani narukvice. Nakon lijepljenja trake nemoguće je prepoznati koje je početno slovo koda, tj. kod na narukvici možemo promatrati kao ciklični niz znakova.

Mirko je prošle godine uspio skinuti svoju narukvicu bez rezanja te ju je sačuvao. Također je uspio doznati \(N\) kodova koji se koriste na ovogodišnjim narukvicama te ga sada zanima može li iz prošlogodišnje narukvice načiniti narukvicu s nekim ovogodišnjim kodom. Prošlogodišnju narukvicu planira razrezati na nekoliko podtraka te dobivene podtrake zalijepiti nekim redoslijedom u novu narukvicu. Podtrake nakon rezanja ne smije okretati jer bi tada neka slova bila naopako što bi zaštitari brzo uočili. Također, Mirko smije rezati prošlogodišnju narukvicu najviše tri puta jer bi više rezova zaštitari lako uočili.

Pomozi Mirku da uđe na festival i odsvira Brandenburški koncert br. 2 na harmonici tako što ćeš za svaki od \(N\) ovogodišnjih kodova napisati može li se dobiti pripadna narukvica gore opisanim postupkom.

ULAZNI PODACI

U prvom retku nalazi se niz od najmanje 3, a najviše 20 malih slova engleske abecede, kod na prošlogodišnjoj narukvici.

U drugom retku nalazi se prirodan broj \(N\) \((1 \leq N \leq 5)\), broj iz teksta zadatka.

U idućih \(N\) redaka nalaze se nizovi znakova sastavljeni od malih slova engleske abecede koji odgovaraju ovogodišnjim kodovima. Njihova duljina bit će jednaka duljini koda s prošlogodišnje narukvice.

IZLAZNI PODACI

U \(i\)-ti \((1 \leq i \leq N)\) redak izlaza potrebno je ispisati “DA” ako se iz prošlogodišnje narukvice može dobiti narukvica s i-tim ovogodišnjim kodom, a “NE” ako ne može.

BODOVANJE

U test primjerima vrijednim 36 bodova vrijedit će za svaki ovogodišnji kod da se može iščitati iz prošlogodišnje narukvice (tj. nije ju potrebno rezati) ili da se ne može dobiti iz prošlogodišnje narukvice

PRIMJERI TEST PODATAKA

Ulaz

ammalislonjas
3
alisamslonjam
malisamjaslon
jasammalislon

Izlaz

DA
NE
DA

Opis prvog primjera

Iz prošlogodišnje narukvice s kodom “ammalislonjas” možemo dobiti narukvicu s ovogodišnjim kodom “alisamslonjam” tako što ćemo jednim rezom dobiti traku na kojoj piše “malislonjasam”, drugim rezom traku ćemo podijeliti na dvije podtrake: “mali” i “slonjasam”, trećim rezom drugu podtraku ćemo podijeliti na dvije: “slonja” i “sam”. Sada lijepljenjem podtraka u redoslijedu “mali”, “sam”, “slonja” dobivamo traku na kojoj piše “malisamslonja” te lijepljenjem početka s krajem dobivamo narukvicu iz koje možemo iščitati ovogodišnji kod. Drugu narukvicu ne možemo dobiti sa samo tri reza, a treća narukvica je jednaka prošlogodišnjoj, tj. nije potrebno rezati prošlogodišnju narukvicu kako bi dobili treću narukvicu.