DMIH 1996., Supetar, 15. - 19. travnja
2. Hrvatska informatička olimpijada
3. zadatak - Križaljka
110 bodova

Na raspolaganju nam je kvadrat koji se sastoji od 25 manjih polja raspoređenih u 5 redaka i 5 stupaca. U ulaznoj datoteci KRIZ.IN nalaze se riječi koje smijemo upotrijebiti kako bi popunili taj kvadrat (križaljku). Svaku riječ smijemo upotrijebiti najviše jednom u križaljci. Neka od polja križaljke smijemo zacrniti. Broj crnih polja nije ograničen, ali bilo koja dva crna polja ne smiju imati zajedničku stranicu, nego se eventualno smiju dodirivati vrhovima. Upotreba crnih polja na rubu križaljke (u 1. i 5. retku, odnosno u 1. i 5. stupcu) je dozvoljena.
Program treba od riječi iz ulazne datoteke probati popuniti križaljku. Sve riječi koje možemo pročitati iz križaljke (to su oni nizovi uzastopnih slova u recima koji su s lijeve i desne strane ograničeni s rubom križaljke ili crnim poljem i nizovi uzastopnih slova u stupcima koji su odozgo i odozdo također ograničeni s rubom križaljke ili crnim poljem) moraju postojati u ulaznoj datoteci.

ULAZNI PODACI

U tekstualnoj datoteci KRIZ.IN nalaze se riječi koje smijemo upotrijebiti u križaljci. U prvoj liniji ulazne datoteke nalazi se broj n koji označava broj riječi u toj datoteci (10 ( n ( 50). Slijedećih n linija ulazne datoteke sadrže n različitih riječi. Jedini dozvoljeni znakovi unutar neke riječi su mala slova engleske abecede (a do z). Duljina riječi će biti manja ili jednaka od 5 znakova.

IZLAZNI PODACI

Ukoliko se križaljka može generirati iz ulaznih podataka, u tekstualnu datoteku KRIZ.OUT treba zapisati jedno od rješenja križaljke. Datoteka KRIZ.OUT tada mora sadržavati 6 linija, u prvoj liniji broj 1, a u slijedećih 5 linija treba zapisati retke iz križaljke tako da svaka linija u izlaznoj datoteci sadrži točno 5 znakova i predstavlja odgovarajući redak iz križaljke. Umjesto crnih polja u križaljci u izlaznu datoteku treba zapisati znak *.
Ako se od ulaznih podataka ne može kreirati križaljka, datoteka KRIZ.OUT se tada mora sastojati od samo jedne linije teksta i u toj liniji mora pisati broj 0.

PRIMJERI

1.)

KRIZ.IN

19
ra
mu
miran
ano
t
ara
gula
dmih
o
a
sir
la
atama
alaga
leon
vujec
am
l
as

KRIZ.OUT

1
atama
l*sir
am*ra
gula*
a*ano

2.)

KRIZ.IN

12
davor
bol
boris
doris
kreso
ormar
usa
shepi
sasa
vesna
tonka
rave

KRIZ.OUT

0

NAPOMENA

Rješenje zadatka snimiti na disk (u direktorij C:(DMIH(HIO) i na disketu (direktorij A:() pod imenom KRIZ.C (odnosno KRIZ.PAS ili KRIZ.BAS). Ukoliko je zadatak riješen u Pascal-u ili C-u, potrebno je u te iste direktorije spremiti izvršnu verziju programa (KRIZ.EXE).

Program mora generirati rješenje unutar 30 sekundi.