Mirko i Slavko igraju sledeću igru: Mirko počinje igru zamišljanjem neke reči.
Međutim, on ne kaže Slavku koju je reč zamislio, već mu kaže samo prvo slovo te reči.
Sada Slavko zamišlja reč koja počinje slovom koje je Mirko rekao i kaže Mirku prva dva
slova svoje reči. Mirko sada opet zamišlja reč koja počinje slovima koje je Slavko rekao
(nova reč može, ali i ne mora biti reč koju je na početku zamislio) i kaže Slavku prva
tri slova. Ova procedura se nastavlja sve dok slova koja kaže Mirko ili Slavko ne formiraju
kompletnu reč. Igrač koji prvi formira kompletnu reč je izgubio igru. To znači iako je Mirko,
na primer, zamislio reč 'lepota' i kaže Slavku prva četiri slova 'lepo' - on gubi, jer je reč
'lepo' takođe reč srpskog jezika.
Kako bi igra bila ravnopravna, oba igrača mogu iskoristiti samo reči iz unapred definisanog
rečnika. Ako oba igrača igraju optimalno, tada je moguće odrediti ko će na kraju igre biti pobednik.
Optimalno igranje podrazumeva da svaki od igrača nastoji da dobije igru u što je moguće manje
poteza (znajuči da će i njegov protivnik takođe igrati optimalno); ukoliko igrač ne može da
dobije igru, onda želi da izgubi što je moguće kasnije.
Krajnji ishod igre je reč iz rečnika koju kaže igrač koji gubi. Ako u nekom momentu nije
bitno za dalji razvoj igre koje slovo će igrač odabrati - on bira uvek slovo koje
dolazi ranije u engleskoj abecedi (leksikografski najmanje). Odrediti koji igrač pobeđuje
u ovoj igri i reč kojom se igra završava.
Ulaz:
(Ulazni podaci se učitavaju iz datoteke igra.in.)
U prvom redu se nalazi prirodni broj n (1 ≤n ≤ 5000). U sledećih n
redova se nalazi po jedna reč sastavljena od malih slova engleske abecede, dužine manje ili jednake
od 50, koja predstavlja reč iz zajedničkog rečnika za oba igrača.
Izlaz:
(Izlazni podaci se ispisuju u datoteku igra.out.) U prvom redu ispisati koji igrač
pobeđuje (1 za Mirka i 2 za Slavka), a u drugom redu ispisati reč kojom se igra završava,
ako oba igrača igraju optimalno.
Primer 1:
igra.in
|
|
igra.out
|
8
avioni
banana
berza
selo
seobe
kosa
kola
kuca
|
|
1
kola
|
Objašnjenje.
Ako Mirko kaže slovo 'b', tada će Slavko pobediti biranjem reči 'berza'
tako što kaže slovo 'e'. Slično, ako Mirko kaže slovo 's', sigurno gubi.
Najzad, Mirko pobeđuje ako zamisli bilo koju reč na 'a' ili 'k'. Ako bi odabrao reč
'avioni' pobedio bi u šest poteza, dok u ostalim slučajevima pobeđuje u 4 poteza. Zato Mirko
bira slovo 'k'. Zatim Slavko bira slovo 'o', pa onda Mirko slovo 'l' (zato sto 'l' dolazi
pre 's' po leksikografskom uređenju) i Slavko slavko na kraju bira slovo 'a'. Dakle, pobeđuje
Mirko (prvi igrač), a tražena reč na kraju igre je 'kola'.
Primer 2:
igra.in
|
|
igra.out
|
3
zzz
zzza
ttt
|
|
2
ttt
|