Šifrovaný text
Zadání
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 šifrovanou 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 textem:
Cannot be decoded
bez úvodních a koncových mezer.
Výstup neobsahuje prázdné řádky.
Příklady
Příklad 1
8
dog
six
is
no
joe
hat
has
fat
kpz ift op ifudog has no hat
dog hat no has
joe has no hat
joe hat no hasPříklad 2
6
what
whale
star
start
ships
float
stay tunedCannot be decodedTestovací 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.