Zadanie

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 roman.sobkuliak@trojsten.sk

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, CZ, AA, AB, ACAZ, BAZZ, AAAANO

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í:

Číslo sady 1 2 3
maximálne \(n\) \(2\,000\) \(6\,000\) \(10\,000\)
maximálne \(x\) \(10\,000\) \(10^8\) \(10^{15}\)

Príklady

Input:

4
5
28
46
100

Output:

E
AB
AT
CV

Input:

3
7629165
265
9062604

Output:

PRASK
JE
SUPER

Dĺžka \(k\)-teho slova

Začneme tým, že si spočítame dĺžku slova na \(k\)-tej pozícii. Napríklad pre \(k = 28\) je hľadaná dĺžka 2, pretože \(28\)-me slovo je AB, ktoré má dve písmená.

Koľko slov má dĺžku 1? Presne 26, sú to jednopísmenové slová AZ. A koľko slov má dĺžku 2? Slovo dĺžky dva dostaneme tak, že vyberieme jedno písmeno na prvú pozíciu a jedno písmeno na druhú pozíciu. Na jednu pozíciu pritom vieme vybrať 26 rôznych písmen a tieto dve pozície sa navzájom neovplyvňujú. Dokopy máme teda \(26 \cdot 26\), teda \(26^2\) možností. Vo všeobecnosti, slov dĺžky \(d\) je \(26^d\). Na každú z \(d\) pozícií totiž môžeme vybrať jedno z 26 písmen.

Teraz si uvedomme, že ak má \(k\)-te slovo dĺžku \(d\), tak v čísle \(k\) sú započítané aj všetky kratšie slová, tie totiž predchádzajú tým s dĺžkou \(d\). V takomto prípade preto vieme, že \(k > 26 + 26^2 + 26^3 \cdots 26^{d-1}\). Súčet na ľavej strane totiž predstavuje počet všetkých slov kratších ako \(d\) – slov dĺžky 1, 2, 3…\(d-1\).

Ak teda chceme zistiť dĺžku \(k\)-teho slova, hľadáme najmenšie \(d\) také, že \(k \leq 26 + 26^2 + \dots + 26^d\). To vieme ľahko výpočítať pomocou jedného while cyklu, v ktorom pripočítavame stále väčšie mocniny 26, až kým nedostaneme číslo väčšie alebo rovné \(k\).

Tento postup si môžeme ilustrovať na nasledovnom príklade:

k = 743

                    26 <  743   // Slovo je dlhsie ako 1
      26 + 26*26 = 702 <  743   // Slovo je dlhsie ako 2
702 + 26*26*26 = 18278 >= 743   // Slovo ma dlzku 3

Prvé písmeno slova dĺžky \(k\)

Úspešne sme zistili dĺžku \(k\)-teho slova, ktorú sme označili \(d\). Poďme sa teda zamerať iba na slová tejto dĺžky. Už vieme, že ich je \(26^d\). Koľké z nich však hľadáme? Nemôže to byť \(k\)-te, pretože v hodnote \(k\) sú zahrnuté aj všetky kratšie slová. Ak teda chceme zistiť, ktoré \(d\) písmenové slovo hľadáme, musíme od \(k\) odpočítať kratšie slová, ktorých je \(26 + 26^2 + \dots + 26^{d-1}\). Nová hodnota \(k\) bude preto rovná tomuto rozdielu.

Pokúsme sa teraz zistiť jednotlivé písmená tohto slova. Zameriame sa na poslednú vlastnosť, ktorú sme ešte nepoužili – abecedné usporiadanie. Vieme, že našich \(26^d\) slov dĺžky \(d\) je usporiadaných abecedne, teda najskôr všetky slová, ktoré začínajú na písmeno A, potom všetky, čo začínajú na B atď. až po Z.

Naviac si uvedomme, že je rovnako veľa slov, ktoré začínajú na A ako tých, ktoré začínajú na B. Ak totiž zoberieme slovo začínajúce na B a toto prvé písmeno zmeníme na A, dostaneme slovo začínajúce na A. Zároveň, dve rôzne slová, ktoré začínajú na B vytvoria dve rôzne slová začínajúce na A. Dokonca, táto vlastnosť platí pre ľubovoľnú dvojicu písmen. Tým pádom je týchto \(26^d\) slov rozdelených na 26 rovnako veľkých skupín, každá s \(26^{d-1}\) slovami. (Tú istú vlastnosť si môžeme uvedomiť aj tak, že ak zafixujeme prvé písmeno, na každú zo zvyšných \(d-1\) pozícií môžeme dať jedno z 26 písmen.)

Ak sa pozeráme iba na \(d\) písmenové slová tak vidíme, že prvých \(26^{d-1}\) začína na písmeno A. Ak je teda \(k \leq 26^{d-1}\), tak prvé písmeno hľadaného slova je A. A ak je \(k\) väčšie, tak môžeme pokračovať. Ďalších \(26^{d-1}\) slov totiž začína na B, takže ak \(k \leq 2\cdot 26^{d-1}\), tak hľadané slovo začína na písmeno B. A keď ani to, môžeme sa pozrieť na písmená C, D

Týmto spôsobom sa určite dopracujeme k prvému písmenu zadaného slova. Ak by sme chceli tento postup naprogramovať, mohli by sme použiť jedoduchý while cyklus, ktorý by skúšal, kam patrí \(k\). Keďže sú však jednotlivé skupiny rovnako dlhé, vieme použiť malý trik. Uvedomme si totiž, že ak sa snažíme zistiť, v ktorej skupine sa nachádza číslo \(k\), je to akoby sme sa pýtali: Koľkokrát sa do čísla \(k\) zmestí \(26^{d-1}\)? A na túto otázku vieme odpovedať pomocou delenia. Je tu len jediný problém. Do čísel 1 až \(26^{d-1}-1\) sa \(26^{d-1}\) zmestí nulakrát, ale do čísla \(26^{d-1}\) sa zmestí raz. A rovnako aj v ostatných skupinách. Aby sme sa tejto nepríjemnosti vyhli, tak nebudeme deliť číslo \(k\), ale číslo \(k-1\). Teraz naozaj platí, že číslo \(\frac{k-1}{26^{d-1}}\) (zaokrúhlené nadol) určuje, do ktorej skupiny patrí hľadané slovo. A tiež poradie prvého písmena tohto slova v abecede.

Ďalšie písmená a kratšie slová

Poznáme dĺžku slova \(d\) a takisto jeho prvé písmeno, nech je to napríklad T. Zvyšok slova už nemusíme preto hľadať medzi všetkými slovami dĺžky \(d\). Stačí sa zamerať na slová dĺžky \(d\), ktoré začínajú na písmeno T. Ktoré z týchto slov hľadáme? Opäť to nebude \(k\)-te z nich. V hodnote \(k\) sú totiž zarátané aj všetky slová dĺžky \(d\), ktoré začínajú na písmeno, ktoré je v abecede skôr ako T. Koľko je takýchto slov?

Písmeno T je dvadsiate v abecede. Pred ním je teda 19 iných písmen (AS). A na každé z týchto písmen začína \(26^{d-1}\) slov dĺžky \(d\). Všetky tieto slová preto musíme od \(k\) odčítať. Nová hodnota \(k\) bude teda \(k - 19\cdot 26^{d-1}\). V tomto momente máme v \(k\) naozaj správnu hodnotu – pozíciu hľadaného slova medzi všetkými slovami dĺžky \(d\) začínajúcich na T.

Chýba nám posledná vec. Všetky slová, ktoré nás zaujímajú začínajú písmenom T. Ako sú teda zoradené? Zoradené sú podľa zvyšných \(d-1\) písmen, ktoré tvoria všetky slová dĺžky \(d-1\) usporiadané podľa abecedy. Naša úloha sa preto nezmení, ak si povieme, že hľadáme \(k\)-te slovo dĺžky \(d-1\). A to je predsa problém, ktorý sme už vyriešili v predchádzajúcej časti.

Vieme, že slová dĺžky \(d-1\) sú rozdelené podľa prvého písmena na 26 skupín, každá po \(26^{d-2}\) slov. A vieme aj to, ako zistiť prvé písmeno \(k\)-teho takéhoto slova. Keď to teda zistíme, toto písmeno bude druhým v poradí v našom pôvodnom probléme. A takisto sa nám problém opäť zmenší na hľadanie \(k\)-teho (pre vhodne upravené \(k\)) slova dĺžky \(d-2\). Tento postup budeme môcť opakovať, zakaždým sa dozvieme o jedno písmeno viac a dĺžka hľadaných slov sa bude znižovať až na 0, kedy už nič nemusíme robiť, pretože také slová neexistujú.

Počet krokov algoritmu

Pozrime sa ešte na časovú zložitosť tohto algoritmu. Ak je dĺžka slova \(d\), tak hľadanie tejto hodnoty bude trvať zhruba \(d\) operácií. A takisto nájdenie hľadaného slova bude trvať zhruba \(d\) operácií, pretože v každom kroku sa o jedna skráti dĺžka slov, na ktoré sa pozeráme. Zostáva zistiť, aká veľká je hodnota \(d\).

Úplne na začiatku sme si ukázali, že platí:

\[k \leq 26 + 26^2 + 26^3 + \dots + 26^d\]

Súčet napravo je počet všetkých slov dĺžky najviac \(d\). Tento súčet je naviac súčet členov geometrickej postupnosti, na ktorý vieme použiť známy vzorec1:

\[k \leq \frac{26^{d + 1} − 26}{25}\]

To znamená, že \(k\) je zhruba tak veľké ako hodnota \(26^{d}\). (Zanedbali sme nejaké konštanty, ktoré sa ale stratia v \(O\)-notácii.) Hodnotu \(d\) preto môžeme slovne popísať ako: číslo, na ktoré keď umocníme číslo \(26\), dostaneme hodnotu \(k\).

No a na vyjadrenie takýchto hodnôt používajú matematici pojem logaritmus. Zapisuje sa to ako \(\log_a{b} = c\), číta sa to ako logaritmus z \(b\) pri základe \(a\) sa rovná \(c\) a vyjadruje to, že ak umocníme hodnotu \(a\) na číslo \(c\) dostaneme číslo \(b\), teda (\(a^{c} = b\)). Časovú zložitosť preto môžeme vyjadriť ako \(O(\log_{26}{k}) = O(\log k)\). Keďže tento výpočet urobíme pre každý riadok vstupu, tak celková zložitosť je \(O(n \cdot \log k)\).

Opäť odporúčam pogoogliť si niečo o logaritmoch, je to v informatike veľmi používaný pojem a oplatí sa poznať vzorce na ich úpravu a vedieť, čo zhruba znamenajú.

#include <iostream>

using namespace std;

void solve() {
    long long k;
    cin >> k;
    long long s = 26, m = 26;

    // Zistenie dlzky slova
    // Premenna s postupne obsahuje pocet slov dlzky 1, 2, 3, atd.,
    // teda ziskava hodnoty 26, 26 + 26^2, atd.
    while (k > s) {
        m *= 26;
        s = s + m;
    }

    // Od k odpocitame vsetky kratsie slova. Nase slovo ma dlzku d,
    // takze kratsich slov bude 26 + 26^2 + ... + 26^(d-1).
    // Staci si uvedomit, ze premenna s obsahuje sumu
    // 26 + 26^2 + ... + 26^(d-1) + 26^d, kde d je dlzka nasho slova.
    // Potrebujeme z nej teda este odpocitat posledny clen 26^d, ale
    // to je prave hodnota v m.
    k = k - (s - m);

    // Nove m obsahuje pocet slov dlzky 26^(d - 1)
    m = m / 26;

    while (m > 0) {
        long long poz = (k - 1) / m;
        cout << (char) (poz + 'A');

        k = k - poz * m;
        m = m / 26;
    }

    cout << endl;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        solve();
    return 0;
}

  1. Ak neviete, čo je geometrická postupnosť, skúste si o nej niečo prečítať.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.