Školska razina 2021 / Osnovna škola (8. razred) - 2. zadatak

Zvjezdan obožava seriju Star Trek. Zato ga je dok je gledao stare zadatke s informatičkih natjecanja obradovala pojava omiljenog lika - Jean-Luca Picarda. Zvjezdan želi igrati Picardovu igru iz zadatka, a tebe moli programski kod kojim će provjeravati svoje rješenje. Zadatak ide ovako:

Jean-Luc Picard je kapetan međuzvjezdanog broda USS Enterprise. Misija ovog broda je uspostavljanje prvih kontakata s drugim vrstama i civilizacijama. Kako bi što bolje mogao komunicirati s novim vrstama, Picard često igra specijalizirane igre s riječima. Opišimo jednu od njih.

U ovoj igri promatramo tablicu s N redaka i M stupaca. Neka polja ove tablice su prazna, a u neka je upisano veliko slovo engleske abecede. Picard želi dopisati što je moguće manje slova u tablicu tako da u nekom retku bude složena unaprijed zadana riječ. Jean-Luc smije dopisivati samo velika slova engleske abecede u prazna polje tablice.

Npr., želi složiti riječ „PICARD“ u tablicu sa slike 1. U prvom retku nije moguće složiti tu riječ, u drugi redak bi trebao dopisati 4 slova (slika 2.) dok bi u treći redak morao dopisati 5 slova (slika 3).

Napiši program koji će za zadane ulazne podatke ispisati poziciju u tablici na kojoj počinje zadana riječ na način kako to Picard želi. Pozicija je određena oznakom retka (1, 2, ..., N) i oznakom stupca (1, 2, ..., M) na čijem se sjecištu nalazi.

Ako ima više takvih mogućnosti, tada treba uzeti onu poziciju koje ima najmanju oznaku retka. Ako ima više takvih mogućnosti, tada treba uzeti onu poziciju koja ima najmanju oznaku stupca. Test primjeri će biti takvi da će uvijek biti moguće dodati traženu riječ u tablicu.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 25), broj iz teksta zadatka.

U drugom je retku prirodan broj M (1 ≤ M ≤ 25), broj iz teksta zadatka.

U sljedećih N redaka nalazi se po M znakova (veliko slovo engleske abecede ili znak „*“ (prazno polje)), pri čemu j-ti znak u i-tom retku predstavlja znak upisan u polje tablice na sjecištu i-tog retka i j-tog stupca u tablici.

U zadnjem je retku string S (1 ≤ duljina(S) ≤ M), zadana riječ

Izlazni podaci

U prvi redak ispiši dva prirodna broja iz teksta zadatka.

Primjeri test podataka

Ulaz

3
7
S**F***
**I*A**
**C***R
PICARD

Izlaz

2 2

Objašnjenje

Opis primjera je dio teksta zadatka

Ulaz

3
7
S**R***
**I*A**
**C***R
STAR

Izlaz

1 1