5. Písmenková šifra vzorové riešenie

4
5
28
46
100

E
AB
AT
CV

3
7629165
265
9062604

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á A až Z. 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 (A až S). 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 vzorec¹:

\[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;
}