Državno natjecanje 2018. / Osnovna škola (6. razred) - 3. zadatak

Državno natjecanje 2018. / Osnovna škola (7. razred) - 3. zadatak

Stjepan i Marin napravili su rječnik koji sadrži N riječi i žele na njegovu naslovnicu staviti nešto prigodno - riječ. Riječ na naslovnici ne mora biti iz tog rječnika te će biti kružnog oblika, kao na slici.

Odlučili su da odabrana riječ mora u sebi sadržavati barem četiri riječi iz njihovog rječnika, tako da se svaka od te četiri riječi može pročitati na nekim uzastopnim pozicijama u kružnoj riječi, u bilo kojem smjeru. Primjerice, kružna riječ sa slike, košarka, sadrži u sebi riječi koš, arka, kako, šok, kraš, itd. Riječ iz rječnika se u kružnoj riječi ne može pročitati ako je dulja od kružne riječi.

Radi zanimljivosti, žele da njihova riječ bude najkraća moguća.

Zadatak je podijeljen u podzadatke označene rednim brojevima od 1 do 3:

1. Riječ koju Stjepan i Marin traže nije kružna te se riječi iz rječnika u njoj mogu čitati samo na uzastopnim pozicijama slijeva nadesno.
2. Riječ koju Stjepan i Marin traže jest kružna, ali se riječi iz rječnika u njoj mogu čitati samo na uzastopnim pozicijama u smjeru kazaljke na satu.
3. Uvjeti su isti kao i u tekstu zadatka.

Napiši program koji na osnovi zadanih ulaznih podataka ispisuje traženu riječ.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj 1, 2 ili 3, redni broj podzadatka.

U drugom retku nalazi se prirodan broj N (4 ≤ N ≤ 6), broj riječi u rječniku.

U sljedećih N redaka nalaze se riječi iz rječnika. Sve će se riječi sastojati od najmanje 3, a najviše 20 malih slova engleske abecede.

IZLAZNI PODATCI

U jedini redak ispišite traženu riječ. Ako postoji više rješenja, ispišite bilo koje.

PRIMJERI TEST PODATAKA

Ulaz

1
4
pptx
cpp
txt
xls

Izlaz

cpptxtxls

Ulaz

2
5
most
rim
stenpri
ten
more

Izlaz

primosten

Ulaz

3
5
kras
sok
arka
kos
kako

Izlaz

kosarka