5. Písmenková šifra

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu arrays_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Romanovi na [email protected]

Andrej a Kika medzi sebou už dlho tajne komunikujú. Ako to už ale so šifrovanými správami býva, šifrovanie a dešifrovanie nie je jednoduché. Boli dni, a nebolo ich málo, keď obaja presedeli celé hodiny nad svojimi šiframi. Keďže najviac času im zaberá dešifrovanie, požiadali vás, aby ste im s touto úlohou trochu pomohli.

Systém ich šifrovania je pomerne jednoduchý. Predstavte si, že zoberieme všetky možné slová zapísané veľkými písmenami anglickej abecedy a tieto slová zoradíme. Zoraďovanie funguje nasledovne: kratšie slová dáme skôr ako dlhšie. V prípade, že sú dve slová rovnako dlhé, ako prvé dáme to, ktoré je skôr v abecede – budeme porovnávať písmená zo začiatku týchto slov až kým nenarazíme na prvú pozíciu, na ktorej sú rôzne. To slovo, ktoré má na tejto pozícii abecedne menšie písmeno zaradíme skôr ako to druhé.

Takýmto spôsobom dostaneme postupnosť všetkých možných slov. Prvé slovo je A, za ním nasleduje B, C … Z, AA, AB, AC … AZ, BA … ZZ, AAA … ANO …

Predložka Z je tak na \(26\)-tej pozícii, zatiaľ čo slovo AHA je \(885.\) v poradí. Na zašifrovanie slova správy potom Andrej s Kikou použijú poradie slova v tejto postupnosti.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane \(n\) čísel. Každé z nich reprezentuje jedno zašifrované slovo správy, teda pozíciu slova v zoradenej postupnosti všetkých slov. Úlohou je rozšifrovať správu, čo znamená nájsť jednotlivé slová v postupnosti.

Formát vstupu

Na prvom riadku je číslo \(n\) – dĺžka správy. Na každom z \(n\) nasledujúcich riadkov je jedno kladné číslo. Každé z týchto čísel zodpovedá jednému zašifrovanému slovu správy.

Formát výstupu

Na \(n\) riadkoch výstupu výpíšte jednotlivé rozšifrované slová zo správy v takom poradí, v akom boli na vstupe.

Pri riešení v jazyku C++, Pascal, Java a podobných si dávajte pozor na maximálne číslo, ktoré sú schopné celočíselné premenné uložiť. Niektoré slová môžu byť zašifrované na veľké čísla prekračujúce tieto limity. Odporúčame preto použiť \(64\)-bitové premenné, v jazyku C++ preto namiesto typu int použite typ long long int.

Riešení v Pythone sa takýto typ obmedzení netýka, pretože premenné v ňom majú neobmedzenú veľkosť.

Hodnotenie

Vaše riešenie bude otestované na troch sadách vstupov. Za vyriešenie každej sady získate 5 bodov. Tieto sady sa líšia veľkosťou vstupných údajov.

V nasledujúcej tabuľke označuje \(n\) dĺžku správy a \(x\) jeden jej prvok, teda jedno zašifrované slovo. Vo vstupných sadách platí:

Príklady

Input:

4
5
28
46
100

Output:

E
AB
AT
CV

Input:

3
7629165
265
9062604

Output:

PRASK
JE
SUPER