Úloha: Šifrovaný text
Obdrželi jsme zašifrovanou zprávu, kterou máme rozšifrovat. Díky činnosti zpravodajů máme k dispozici dodatečné informace, které nám pomohou zjistit text zprávy. Víme, že šifra je neobyčejně jednoduchá, je to pouze permutace 26 písmen anglické abecedy. To ale samo o sobě dosti dobře nestačí. Permutací 26 prvků je 26! = 403291461126605635584000000, což je alespoň tisíckrát více než počet hvězd v pozorovatelném vesmíru. Nelze tedy počítat s tím, že bychom vyzkoušeli všechny permutace a vybrali tu, která produkuje srozumitelný text. Podařilo se však získat kompletní seznam všech slov (slovník), které se vůbec mohou v jakékoli zprávě před jejím zašifrováním vyskytnout. Je tedy jisté, že v zašifrované zprávě existuje ke každému zašifrovanému slovu jeho protějšek ve slovníku. Takto vybaveni již můžeme přistoupit k dešifrování. Je možné, protože šifru neznáme, že danou zašifrovanou zprávu lze pomocí slovníku interpretovat více způsoby.Pro šfrovanou i dešifrovanou zprávu se používá pouze 26 znaků malé anglické abecedy a znak mezera.
Vstup
Na vstupu je nejprve řádek s celým kladným číslem udávajícím počet slov ve slovníku. Dále následuje seznam všech slov ve slovníku, na každém řádku jedno slovo. Slova mohou být uvedena v libovolném pořadí. Za seznamem na dalším řádku je uveden text šifrované zprávy. Řádek neobsahuje počáteční ani koncové mezery, slova v šifrovaném textu jsou oddělena jedinou mezerou, jiné mezery vstup neobsahuje. Vstup neobsahuje prázdné řádky. Délka každého slova je nejvýše 30 znaků, slovník obsahuje nejvýše 100 000 slov. Všechna slova ve slovníku jsou navzájem různá. Zpráva má nejvýše 100 000 slov.Výstup
Na výstupu je seznam všech možných variant dešifrované (= původní) zprávy, seřazený ve vzrůstajícím abecedním pořadí. Každá varianta je uvedena na samostatném řádku a je formátována stejně jako šifrovaná zpráva. Pokud zprávu s použitím slovníku dešifrovat nelze, obsahuje výstup jediný řádek s textemCannot be decoded
bez úvodních a koncových mezer. Výstup neobsahuje prázdné řádky.
Příklad 1
Vstup:8 dog six is no joe hat has fat kpz ift op ifuVýstup:
dog has no hat dog hat no has joe has no hat joe hat no has
Příklad 2
Vstup:6 what whale star start ships float stay tunedVýstup:
Cannot be decoded
Testovací data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
b