4. Ondrej odpúšťa vzorové riešenie

1 2 3 4 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29 ...

... 491 492 493 494 496 497 498 499 600 601 602 603 604 606 ...

5
0
1
4
17
19

1
2
6
4
6

Úlohou bolo čo najrýchlejšie zistiť \(k\)-tu cifru v Zajovom zošite. Tam sa jedno za druhým nachádzajú všetky prirodzené čísla, v ktorých sa nenáchádza cifra \(5\), počínajúc jednotkou.

Keby sme nemuseli vynechávať tú päťku, tak by to bolo ľahšie, nemyslíte?

Ako sa vysporiadať s päťkou

Vynechávanie päťky nám nerobí až taký veľký problém. V prvom rade si uvedomme, že vynechávame všetky celé čísla, ktoré obsahujú cifru päť. Nevynechávame len jednotlivé cifry.

Tým sa dostávame dočinenia s prirodzenými číslami, ktoré sa skladajú z cifier \(0, 1, 2, 3, 4, 6, 7, 8, 9\).

Vidíte to? Deväť rôznych cifier. Idú jedna po druhej. Po \(2\) ide \(3\), po \(4\) ide \(6\).

V skutočnosti jednáme s číslami zapísanými v deviatkovej sústave!

Aby to bolo zrejmejšie, stačí cifry \(6, 7, 8, 9\) prepísať na cifry \(5, 6, 7, 8\). Tým sa reálne nič nezmení, len sme si premenovali cifry. Teraz už pracujeme s ciframi \(0, 1, 2, 3, 4, 5, 6, 7, 8\).

Trošku praktickej ukážky. Poďme zistiť, ktoré číslo (celé číslo, nie len cifra) je \(31728\)-té v poradí v Zajovom zošite. Najprv musíme zistiť, ktoré prirodzené číslo je \(31728\)-té v deviatkovej sústave. To zistíme jednoducho tak, že prepíšeme desiatkové číslo \(31728_{10}\) do deviatkovej sústavy. Dostaneme \(47463_9\). Teraz sme dostali hľadané číslo, len v skutočnej deviatkovej sústave. Skutočná deviatková sústava v podstate vynecháva cifru \(9\), my vynechávame cifru \(5\). Preto musíme cifry väčšie ako \(4\) zväčšiť o jedna. Hľadaným číslom je teda číslo \(48473\).

Hrubá sila

Najjednoduchšie riešenie je priamočiaré generovanie jednotlivých cifier, až kým nevygenerujeme hľadanú cifru, ktorú následne vypíšeme ako výstup. Postupne ideme cez prirodzené čísla od 1. Každé skonvertujeme do deviatkovej sústavy a dané cifry pripíšeme na koniec poľa, kde si pamätáme všetky cifry v Zajovom zošite v poradí. Cifry väčšie ako \(4\) zväčšíme o \(1\). Keď sa už v poli nachádza dostatok cifier, aby sme vedeli zodpovedať otázku na vstupe, prestaneme generovať a vypíšeme odpoveď. Keďže cifry v Zajovom zošite sú vždy také isté, dané pole cifier si môžeme pamätať medzi otázkami, čím si ušetríme kopu času, ktorý by sme zabili generovaním tých istých cifier viac krát.

Aká je časová zložitosť tohto riešenia? Každú cifru musíme osobitne vygenerovať a umiestniť do poľa. Ak chceme povedať ako vyzerá \(k\)-ta cifra, musíme vygenerovať všetkých prvých \(k\) cifier. Keďže si však pole pamätáme medzi otázkami, každú cifru vygenerujeme len raz. Časová zložitosť je preto \(O(n + k)\), kde \(n\) je počet otázok a \(k\) je maximálna cifra v otázke.

Takáto časová zložitosť je dostatočná pre prvú sadu vstupov. Je však celkom zrejmé, že pri \(k = 10^{18}\) nám to už stačiť nebude.

Chytré triky na druhú a tretiu sadu

V zadaní bolo napísané, že druhú a tretiu sadu vstupov sa dalo riešiť nejakými trikmi. A je to pravda!

V druhej sade si musíme všimnúť dôležitú vec: existuje len \(257\) možných otázok. Môžeme si teda všetky tieto vstupy dopredu predrátať na vlastnom počítači s neobmedzeným časovým limitom. Potom ich napíšeme priamo do zdrojového kódu programu a okamžite ich vypíšeme na požiadanie.

V tretej sade tiež nie je veľa možných vstupov: \(10^5\). To už je však priveľa na to, aby sme ich písali na tvrdo do zdrojového kódu. Všimnime si však inú vec. Máme dočinenia s ciframi s indexami od \(10^9\) do \(10^9 + 10^5\). Všetky cifry sa nachádzajú vnútri 9-ciferných čísel v Zajovom zošite. (Ak neveríte, overte si). Spočítaním počtov cifier v jednotlivých rádoch (jednociferné, dvojciferné, …) vypočítame, že prvá cifra nachádzajúca sa v prvom 9-cifernom čísle je cifra číslo \(338992928\).

A teraz prichádza veľká myšlienka. Jednáme iba s ciframi 9-ciferných čísel a vieme, ktorá cifra je prvá cifra prvého 9-ciferného čísla. Teda, keď dostaneme číslo cifry, ktorú máme vypísať, vieme ľahko vypočítať, v ktorom 9-cifernom čísle sa táto cifra nachádza.

Napríklad, povedzme, že máme vypísať cifru číslo \(1000008371\). Odčítaním \(1000008371 - 338992928 = 661015443\) zistíme, koľkatá cifra v 9-ciferných číslach to je. Teraz, keďže všetky 9-ciferné čísla sú rovnako dlhé, celočíselným delením \(661015443 / 9 = 73446160\) vypočítame, v koľkatom 9-cifernom čísle sa táto cifra nachádza. Je to číslo \(263173164\) (v deviatkovej sústave). Ako sme už raz spravili, keďže my vynechávame cifru \(5\), poposúvame všetky cifry väčšie ako \(4\) o jedna a jedná sa teda o číslo \(273183174\) v Zajovom zošite. Ďalej, pomocou zvyšku po delení \(661015443 \mod 9 = 3\) ľahko zistíme, že hľadaná cifra je štvrtá v danom čísle. Správna odpoveď je teda \(1\).

Vzorové riešenie

Od triku, ktorý sme použili v tretej sade nám ostáva už len krôčik k vzorovému riešeniu. V tretej sade nám pomohlo, že sme vedeli koľko ciferné je číslo, v ktorom sa nachádza hľadaná cifra. Nevedeli by sme túto informáciu vypočítať pre ľubovoľnú cifru? Samozrejme, vedeli.

Stačí, keď si predpočítame indexy prvých cifier v každom ráde: v 1-ciferných, 2-ciferných, 3-ciferných, a tak ďalej, až po 18-ciferné (s väčšími totiž nebudeme mať do činenia). Potom, keď dostaneme index cifry, ktorej hodnotu máme vypísať, stačí zistiť, medzi ktorými dvoma začiatkami sa jej index nachádza a podľa toho zistíme, v koľkocifernom čísle ju hľadať. Napríklad, cifra s indexom \(4321\) sa nachádza v nejakom 4-cifernom čísle, pretože prvá cifra zo štvorciferného čísla má index \(2096\) a prvá cifra 5-ciferného čísla má index \(25424\). Index \(4321\) sa nachádza medzi týmito dvoma začiatkami, preto vieme, že sa jedná o cifru 4-ciferného čísla.

Keď zistíme, v koľkocifernom čísle sa hľadaná cifra nachádza, použijeme rovnaký postup, ako pri tretej sade, len ho zovšeobecníme na ľubovoľný počet cifier.

Časová zložitosť

Aká je časová zložitosť tohoto riešenia? Pre každú otázku potrebuje spraviť tri veci:

1. Nájsť rád čísla, v ktorom sa nachádza daná cifra.
2. Vypočítať, v ktorom čísle sa daná cifra nachádza.
3. Vypočítať, koľkatá cifra to je, čím už vieme vypočítať konkrétnu cifru.

Časová zložitosť krokov 2. a 3. je jasná: \(O(1)\). Koľko nám trvá nájsť rád cifry? Vzhľadom na limity na veľkosť vstupu, počet možných rádov je najviac \(18\). Pre zjednodušenie môžeme teda povedať, že nájsť rád trvá \(O(1)\).

Pokiaľ by však veľkosť čísel na vstupe bola neobmedzená, museli by sme započítať aj nejaké logaritmy navyše. Takéto logaritmy by sme však museli potom započítať aj do krokov 2. a 3.

Celková časová zložitosť je teda \(O(n)\).

#include <bits/stdc++.h>
using namespace std;

long long devat_na[18];
long long zaciatok_i_cifernych[19];

void predrataj()
{
	devat_na[0] = 1;
	for(int i=1; i<18; i++)
	{
		devat_na[i] = devat_na[i-1] * 9;
	}
	
	long long cifier_zatial = 0;
	for(int i=1; i<=18; i++)
	{
		zaciatok_i_cifernych[i] = cifier_zatial;
		long long pocet_i_cifernych = 8 * devat_na[i-1];
		cifier_zatial += pocet_i_cifernych * i;
	}
}

vector<int> do_deviatkovej_sustavy(long long x)
{
	vector<int> vysledok;
	while(x > 0)
	{
		vysledok.push_back(x % 9);
		x /= 9;
	}
	reverse(vysledok.begin(), vysledok.end());
	return vysledok;
}

int main()
{
	predrataj();
	
	int n;
	cin >> n;
	for(int test = 0; test < n; test++)
	{
		long long k;
		cin >> k;
		int kolko_ciferne;
		for(int i=18; i>=1; i--)
		{
			if(zaciatok_i_cifernych[i] <= k)
			{
				kolko_ciferne = i;
				break;
			}
		}
		long long kolke_i_ciferne = (k - zaciatok_i_cifernych[kolko_ciferne]) / kolko_ciferne;
		long long ake_cislo = devat_na[kolko_ciferne-1] + kolke_i_ciferne;
		
		vector<int> v_deviatkovej = do_deviatkovej_sustavy(ake_cislo);
		int kolka_cifra = (k - zaciatok_i_cifernych[kolko_ciferne]) % kolko_ciferne;
		if(v_deviatkovej[kolka_cifra] >= 5)
		{
			printf("%d\n", v_deviatkovej[kolka_cifra]+1);
		}
		else
		{
			printf("%d\n", v_deviatkovej[kolka_cifra]);
		}
	}
	return 0;
}