Změny směru
Obdélníková oblast je rozdělena na čtvercová pole a má M řádků a N sloupců. Každé pole obsahuje jeden znak abecedy {a, b, c, ..., z}.Na poli v levém horním rohu oblasti stojí robot. Robot se smí pohybovat pouze tak, že v každém kroku přejde na sousední pole směrem doprava nebo dolů. Pohyb úhlopříčně, nahoru nebo doleva je vyloučen. Pohyb povinně končí na poli v pravém dolním rohu oblasti.
Pokud během pohybu robot opustí některé pole stejným směrem, jakým do něj přišel, tj. přijde shora a pokračuje dolu nebo přijde zleva a pokračuje doprava, vypíše se na výstup robota znak uložený v tomto poli. Pokud během pohybu robot opustí některé pole jiným směrem, než jakým do něj přišel, tj. přijde shora a pokračuje doprava nebo přijde zleva a pokračuje dolů, vypíše se dvakrát za sebou na výstup robota znak uložený v tomto poli. Znak uložený v prvním a posledním poli cesty robota se na výstup robota nevypisuje.
Za jednu cestu robota budeme považovat posloupnost všech polí, které robot navštíví během svého pohybu z horního levého do pravého dolního rohu oblasti. Všimněte si, že všechny možné cesty robota mají stejnou délku, rovnou M + N −1.
Dvě cesty robota budeme považovat za různé, pokud se příslušné posloupnosti navštívených polí liší alespoň v jednom svém prvku.
Například v oblasti o rozměru 3×5 je možných celkem patnáct různých cest.
|
| Obr. 1. Příklad. Pro oblast na obrázku a pro cestu popsanou posloupností kroků (doprava, doprava, dolů, doprava, doprava, dolů) se na výstupu robota objeví řetězec baazzabb. |
Kromě uvedených pravidel je pohyb robota dále omezen tím, že během své cesty z horního levého do pravého dolního rohu oblasti musí změnit směr svého pohybu přesně K-krát, kde K je pevně dané kladné celé číslo.
Robot je naprogramován tak, že koná cesty z horního levého do pravého dolního rohu oblasti opakovaně, ale pokaždé volí takovou cestu, která se liší od všech předchozích. Každá cesta je charakterizována jedním řetězcem skládajícím se ze znaků, které byly vypsány na výstup robota během jeho pohybu po této cestě. Práce robota končí, když projde všechny možné cesty (s ohledem na daná omezení) a na výstupu robota se objeví všechny jim příslušné řetězce.
Úloha
Máme najít a vypsat takový řetězec, který se na výstupu robota objeví nejčastěji během jeho práce. Pokud je více takových řetězců, které se na výstupu robota objeví se stejnou maximální četností, vypíšeme je všechny v rostoucím abecedním pořadí.
Vstup
Na vstupu je více řádků. První řádek obsahuje čísla M, N, K v tomto pořadí oddělená mezerou. Dále následuje M řádků, každý řádek obsahuje jeden řetězec délky N a představuje jeden řádek oblasti s uvedenými znaky v jednotlivých polích. Nejprve je na vstupu nejhořejší řádek oblasti, pak další řádek pod ním atd. Vstup neobsahuje prázdné řádky.Hodnota M a N nepřekročí 100, hodnota K je volena tak, že vždy existuje alespoň jedna cesta z levého horního do pravého dolního rohu oblasti s právě K změnami směru. Počet všech možných cest robota nepřekročí 110 000.
Výstup
Na výstupu je jeden nebo více textových řádků. Každý řádek představuje jeden výstupní řetězec charakterizující jednu cestu robota. Řádky jsou uspořádány v rostoucím abecedním pořadí a obsahují právě všechny výstupní řetězce, které se na výstupu robota objeví se stejnou maximální četností.Příklad 1
Vstup:4 6 2 aaaaba acaaaa baaaab aaaabaVýstup:
aaaaaaaab aacaaaaab
|
| Obr. 2. Ilustrace k příkladu 1. Levá dvě schémata znázoňují dvě cesty, které jsou obě charakterizovány řetězcem aaaaaaaab, pravá dvě znázoňují dvě cesty, které jsou obě charakterizovány řetězcem aacaaaaab. Zbylé dvě možné cesty jsou charakterizovány unikátnímí řetězci aaabbaabb a abbaaaabb a ve výstupu našeho programu se neobjevují. |
Příklad 2
Vstup:3 6 3 abbbba bbabba abbbaaVýstup:
bbbbbbbaaUvedeným řetězcem na výstupu jsou charakterizovány dvě různé cesty. Z ostatních šesti cest má káždá svůj unikátní řetězec.
Příklad 3
Vstup:18 11 7 ooiitoitioo xoxtoixxixt txiiiittixi toiixitixxi ootooittotx ottiitxitix ittttoxoixo totoootttix xtttixitiot tiioioxioii xoxoxitxotx iiitxtoioii iottootoitx totiiioiixt xxxxtitioox toottoxottt xoiotiixtit ixtitoxioooVýstup:
xttoootttttttoooottixtototxixxioo xttoootttttttooootttiioititxotioo xttoootttttttoooottttioooiiottooo xttoootttttttoooottttixioiioxiioo