Počet bodov:
Program:  15b

Táto úloha sa dá nahradiť riešením sady conditions_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, alebo máte napríklad problémy s načítaním vstupu, napíšte Andrejovi na

Žaba sa po sústredení opäť zastavil doma v Lučenci. Pri obede sa pochválil ako bolo na sústredení super a čo všetko sa deti naučili. Všetci pri stole boli ohromení.

Jedine babka ostala skeptická a pochybovačne odvetila: “Algoritmy, polia, časová zložitosť… Zaujímavé to veci, ale povedz mi Miško, dokážu sa tie vaše decká popasovať aj s nejakým skutočným problémom?”

Žabovi sa začali potiť dlane a potichu uvažoval, na čo môže babka narážať. Ak by chcela šľachtiť kvetiny, tak decká naučil algoritmus na porovnávanie DNA, takže by to malo byť v pohode. A keby chcela robiť vzory na vyšívanie, tak na to spravila jeho spolužiačka ako bakalársku prácu aplikáciu1. Ale ak to bude niečo iné…

Pri stole nastalo hrobové ticho. Babke po chvíli premýšľania skĺzli oči na noviny a v nich vidí poslednú nevyriešenú osemsmerovku. V tom jej zablysnú oči.

“A povedz mi Miško, dokázali by tie tvoje deti vyriešiť moje osemsmerovky? S niektorými si ozaj neviem dať rady,” pýta sa babka.

Žaba neváhal a prijal babkinu výzvu.

Pre tých, ktorí nie sú úplne oboznámení s touto hrou: Ide o hru, kde dostanete mriežku písmen a niekoľko slov. V mriežke písmen sa snažíte nájsť a vyškrtnúť zadané slová. Ako už názov napovedá, slová sa môžu v mriežke nachádzať vo ôsmich základných smeroch. Po vyškrtaní všetkých slov ostanú niektoré písmená nepreškrtnuté. Keď si ich zapíšete v poradí odhora dole a zľava doprava, dostanete riešenie osemsmerovky. Zväčša je to odpoveď k nejakej hádanke alebo vtipu.

Úloha

Na vstupe dostanete osemsmerovku a zoznam slov, ktoré v nej máte nájsť. Vašou úlohou je nájsť riešenie osemsmerovky, teda písmená, ktoré ostanú po vyškrtaní všetkých týchto slov.

Slovo v osemsmerovke je postupnosť písmen v jednom z ôsmich smerov. Je zaručené, že žiadne slovo sa v osemsmerovke nenachádza viackrát. Slová sa môžu v osemsmerovke prekrývať, avšak platí, že žiadne nie je úplne prekryté iným slovom.

Vstup

Na prvom riadku vstupu dostanete tri čísla: \(r\), \(s\) a \(n\). Číslo \(r\) určuje počet riadkov a číslo \(s\) počet stĺpcov osmesmerovky. \(n\) je počet slov, ktoré je v osemsmerovke treba vyškrtnúť.

Na každom z ďalších \(r\) riadkov je \(s\) znakov, ktoré popisujú samotnú osemsmerovku. Nakoniec je na vstupe \(n\) slov, každé na samostatnom riadku.

Znaky na vstupe predstavujúce osemsmerovku a hľadané slová sú malé písmená anglickej abecedy.

Pri riešení v jazyku C++ vám odporúčame využiť dátovú štruktúru string. K jej použitiu je potrebné na začiatok vášho programu pridať #include<string>. Do stringu potom viete pomocou cin >> načítavať vstup a pracovať s ním ako s poľom, v ktorom je na každej pozícii jeden znak (typ char).

Opäť pripomíname, že ak by ste mali problémy s načítavaním a spracovaním vstupu, či už v C++, Pythone alebo niečom inom, napíšte Andrejovi.

Výstup

Na výstup vypíšte písmená, ktoré ostali po vyškrtaní všetkých slov, v poradí, v akom by ste ich čítali pri klasickej osemsmerovke. Výstup ukončite znakom konca riadku.

Hodnotenie

Vaše riešenie bude hodnotené na viacerých sadách testovacích vstupov. V preklade to znamená, že aj pomalšie korektné riešenia dostanú nejaký počet bodov a teda sa ich oplatí odovzdať.

Vo všetkých sadách bude platiť, že \(r,s \leq 100\) a \(n \leq 40\). Zároveň platí, že celkový súčet dĺžok slov neprekročí \(400\).

V jednotlivých sadách platia nasledujúce obmedzenia:

  • V prvej sade platí, že \(r = 1\) a \(n = 1\). Osemsmerovka má teda iba jeden riadok a hľadáte v nej iba jedno slovo.

  • V druhej sade platí, že \(r = 1\). Osemsmerovka má iba jeden riadok, hľadáte v nej však viacero slov.

  • V tretej sade platí, že \(n = 1\). To znamená, že hoci osemsmerovka môže byť ľubovoľne veľká, vy v nej budete hľadať iba jediné slovo.

  • V štvrtej sade platí, že \(r \cdot s \leq 50\). Teda osemsmerovka bude relatívne menšia.

  • Pre piatu sadu neplatia žiadne špeciálne obmedzenia.

Za vyriešenie každej z týchto sád získate 3 body.

Príklady

Input:

9 9 15
zapamkacg
kkjadrorn
ioyrylati
askznmaes
stssaiyhu
erttmjpsl
railistrk
dkonkalvy
aaskatsec
adresa
cesta
cyklus
dynamika
gramatika
halda
jadro
jazyk
kostra
list
mapa
mys
skok
tok
vlakno

Output:

zacniriesitprask

Táto osemsmerovka sa nachádzala na letáku PRASKu

Input:

5 4 3
ccxb
xabf
xaxf
xaxf
xaxf
abb
aaaa
cc

Output:

xxfxxfxxfxxf

  1. True story.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.