Zadanie

Vlejdovi sa veľmi zapáčila úloha Zwarte doos z minulej série. Hneď vyriešil všetkých desať hlavolamov. Bohužiaľ, potrvá celkom dlho kým zwarte doos načerpá novú inšpiráciu a vymyslí nové hlavolamy. Preto sa Vlejd od nudy začal zamýšľať, ako taká zwarte doos funguje. Najviac sa mu zapáčil šiesty level z prvej série. Zistil, že krabička vie celkom rýchlo odpovedať aj keď do nej hodí veľmi veľké číslo. Rozhodol sa, že si to vyskúša naprogramovať.

Úloha

Predstavte si, že zoberiete všetkých 26 veľkých písmen anglickej abecedy a poskladáte z nich všetky možné slová. Tieto slová potom zoradíte. Najskôr podľa dĺžky a potom podľa abecedy. Takto získate postupnosť, ktorej prvky vám vracala šiesta krabička. Prvé slovo je A a za ním nasledujú B, C, …, Z, AA, AB, AC, AZ, BA, …, ZZ, AAA, …

Vašou úlohou bude urobiť program, ktorý na vstupe dostane číslo \(n\) a vypíše \(n\)-té slovo vyššie spomenutej postupnosti. Pre \(1\) má teda vypísať A, pre \(28\) AB

Vstup

Na prvom riadku vstupu je \(1 \leq t \leq 10\,000\) – počet otázok pre krabičku. V každom z nasledujúcich \(t\) riadkov sa nachádza číslo \(1 \leq n \leq 10^{15}\).

Výstup

Pre každú otázku vypíšte \(n\)-té slovo postupnosti.

Príklady

Input:

5
2
1
4961867752
47
7946

Output:

B
A
PAPAGAJ
AU
KSP

Začneme tým, že si spočítame akú dĺžku má \(n\)-té slovo. Slov dĺžky \(1\) je \(26\). Slov dĺžky \(2\) je \(26 \cdot 26\), lebo na prvej pozícii môže byť \(26\) rôznych písmen a na druhej môže byť tiež \(26\) písmen. Vo všeobecnosti, slov dĺžky \(k\) je \(26^k\). Takže v cykle budeme postupne odčítavať počty slov dĺžky \(i\) od \(n\) kým bude platiť, že \(n > 0\). Ak totiž platí \(n - 26^i > 0\)1, tak sa hľadané slovo nachádza v postupnosti až za všetkými slovami dĺžky \(i\), čiže musí byť nutne dlhšie ako \(i\). Ak \(n - 26^i \leq 0\), tak to znamená, že hľadané slovo má dĺžku \(i\).

V ďalšej fáze zistíme, z akých písmen sa toto slovo skladá. Nech je naše slovo dĺžky \(d\). Potom všetkých slov dĺžky \(d-1\) je \(26^{d-1}\). Teda slov dĺžky \(d\) začínajúcich na písmeno A je \(26^{d-1}\). Zasa by sme mohli v cykle odčítavať počty slov začínajúcich na písmeno A, potom na písmeno B, písmeno C atď. Myšlienka je rovnaká ako pri hľadaní dĺžky.

Všimnite si, že zakaždým odčítavame to isté číslo číslo, takže rozumnejšie bude použiť celočíselné delenie. Teda \(n/26^{d-1}\) hovorí, koľkokrát môžeme odčítať \(26^{d-1}\) od \(n\) aby sme neklesli pod \(0\) a zvyšok po delení je to čo nám z \(n\) ostane po odčítavaní. Takýmto spôsobom zistíme každé písmeno slova. (V zdrojovom kóde, ktorý sa nachádza nižšie sme využili to, že hodnoty \(26^{d-1}\) sme si predpočítali dopredu v predchádzajúcom cykle.)

Pamäťová zložitosť je zjavne \(O(1)\), lebo sme na zapamätávanie použili len pár premenných.

Pozrime sa na časovú zložitosť tohto algoritmu. Nech dĺžka slova je \(d\). Potom aj prvý, aj druhý cyklus urobí zhruba \(d\) operácii. Poďme spočítať aké veľké je číslo \(d\). Z predchádzajúceho algoritmu pre \(d\) a \(n\) platí:

\[n \leq 26^0 + 26^1 + \dots + 26^d\]

Toto nie je nič iné ako súčet členov geometrickej postupnosti na čo použijeme vzorec2:

\[n \leq \frac{26^{d+1}-1}{25}\]

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

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ím hodnotu \(a\) na číslo \(c\) dostanem číslo \(b\) (\(a^c=b\)). Časovú zložitosť preto môžeme vyjadriť ako \(O(\log_{26} n) = O(\log n)\). Keďže tento výpočet urobíme pre každý riadok vstupu, tak celková zložitosť je \(O(t \log n)\).

Opäť si odporúčam pogoogliť 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 <cstdio>

void solve()
{
	long long N;
	scanf("%lld",&N); N++;
	long long words = 1;
	//zistime dlzku
	while (N - words > 0)
	{
		N -= words;
		words *= 26;
	}
	words /= 26;//2^d
	N--;
	while (words)
	{
		putchar( N / words + 'A');
		N %= words;
		words /= 26;
	}
	putchar('\n');
}

int main()
{
	int T;
	scanf("%d",&T);
	for (int i=0;i<T;++i) solve();
	return 0;
}

  1. Uvedomte si, že hodnota \(n\) v tejto nerovnici vyjadruje pôvodnú hodnotu \(n\), od ktorej sme už odčítali všetky menšie mocniny \(26\).

  2. Odporúčam vygoogliť.

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ť.