Županijsko natjecanje 2012. / Osnovna škola (6. razred) - 3. zadatak

Županijsko natjecanje 2012. / Osnovna škola (7. razred) - 2. zadatak

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 imamo tablicu koja ima n redaka i m stupaca tj. nxm polja.

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., on želi da složi riječ „PICARD“ u nekom retku tablice s 3 retka i 7 stupaca sa slike 1.

U prvom retku nije moguće složiti tu riječ, u drugi redak bi trebao dopisati 4 slova dok bi u treći redak morao dopisati 5 slova.

Na slici 2. su prikazane sve te mogućnosti dok slika 3. prikazuje optimalni zapis.

Međutim, ponekad se dogodi da uopće nije moguće složiti zadanu riječ u tablici.

Tada Jean-Luc uzme gumicu, obriše neka ranije upisana slova i uspješno složi zadanu riječ.

Prilikom brisanja on uvijek želi obrisati što manje tih upisanih slova.

Napiši program koji će za zadano početno stanje u tablici i dodatnu riječ odrediti poziciju polja na kojem nakon dopisivanja slova započinje pojavljivanje te riječi u tablici.

Pozicija polja 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.

U slučaju da postoji više takvih u istom retku, tada treba uzeti onu koja ima najmanju oznaku stupca.

U slučaju kada je potrebno brisanje slova, tada treba odrediti najmanji broj slova koje je trebalo obrisati da bi se zadana riječ mogla složiti u tablici.

Ulazni podaci

prirodan broj N ( 1 ≤ N ≤ 25), broj redaka u tablici;

prirodan broj M ( 1 ≤ M ≤ 25), broj stupaca u tablici;

u sljedećih N redaka se nalazi po M znakova (znak može biti 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;

string S ( 1 ≤ duljina(S) ≤ M ), zadana riječ.

Izlazni podaci

tekst „DA“ i dva prirodna broja odvojena razmakom koji predstavljaju poziciju polja ili tekst „NE“ i jedan prirodan broj koji predstavlja minimalnih broj obrisanih slova iz tablice.

Napomena: u test primjerima vrijednima 30% bodova, morat će se brisati slova u tablici

Primjeri test podataka

Ulaz

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

Izlaz

DA 2 2

Objašnjenje

Ovaj primjer je opisan u zadatku.

Ulaz

3
7
S*P*R*T
*KI*AB*
D*C***R
PICARD

Izlaz

NE 1