Zadanie

,,Vyberme si nejaké náhodné číslo, napríklad päť. Hm, to je málo, päťdesiat päť,’’ začal Ondrej Demáček vysvetľovanie nového zaujímavého algoritmu na hodine informatiky. Táto programátorská legenda už celé desaťročia nezlyhala v upútavaní pozornosti svojich študentov.

Až na Zaja. Zajo ten algoritmus už totiž poznal a tak sa mimoriadne nudil. Hojdal sa na stoličke, šepkal spolužiakom trápne vtipy, hádzal zožmolené kusy papiera do koša za dverami triedy, skrátka, robil neporiadok. Každému by z toho praskli nervy. Aj Demáčkovi.

,,Zajo! Vyrušuješ! Tu máš prázdny zošit, mazaj za dvere a napíš doňho všetky prirodzené čísla od jedna po milión.’’

Zajo sklopil uši, zobral zošit do ruky a vyšiel za dvere. Spoza dverí začul ešte Demáčka: ,,Kto túto úlohu vyrieši ako prvý, dostane celú túto tabuľku čokolády’’.

,,Ale no tak,’’ pomyslel si Zajo. ,,Zaručene by som to vyriešil prvý. Mohol som mať čokoládu. Keby ten starý… musím sa mu nejako pomstiť… už viem! Keď už má tak rád to číslo päť, v tomto zošite ho nenájde. Napíšem sem všetky čísla od jedna po milión, okrem tých, ktoré obsahujú cifru päť. Pche, a načo sa zastavovať na milióne? Však ja mu ukážem!’’

S novým nadšením sa Zajo pustil do práce.

Úloha

Zajo do svojho zošita píše za sebou prirodzené čísla od 1. Demáček mu dal za úlohu len do milión, Zajo sa však rozhodol, že sa nikdy nezastaví v písaní. Zajo pri tom vynecháva všetky čísla, ktoré obsahujú cifru 5.

Začiatok jeho zošita teda vyzerá takto:

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

A keď prelistujeme zopár strán ďalej, tak to vyzerá takto:

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

Dostanete číslo \(k\). Vašou úlohou je zistiť hodnotu \(k\)-tej cifry napísanej v Zajovom zošite. Číslujeme od nuly.

Formát vstupu

Každý testovací vstup obsahuje otázky na niekoľko cifier v Zajovom zošite. Na prvom riadku vstupu sa nachádza počet týchto otázok, celé číslo \(n\). Nasleduje \(n\) riadkov. V \(i\)-tom z nich sa nachádza celé číslo \(k_i\) – číslo cifry, ktorá nás zaujíma v \(i\)-tej otázke. Platí \(1 \leq n \leq 10^5\) a \(0 \leq k_i \leq 10^{18}\).

Sú 4 sady testovacích vstupov. Pre jednotlivé sady navyše platia nasledovné obmedzenia:

číslo sady \(1\) \(2\) \(3\) \(4\)
\(n \leq\) \(10^3\) \(10^5\) \(10^5\) \(10^5\)
\(k_i \geq\) \(0\) \(10^9\) \(10^9\) \(0\)
\(k_i \leq\) \(10^5\) \(10^9 + 256\) \(10^9 + 10^5\) \(10^{18}\)

Pozor! Druhá a tretia sada majú špeciálne limity na \(k_i\). Ak aj nevyriešite úlohu optimálne, za kreatívne vyriešenie druhej a tretej sady a následné popísanie vášho postupu môžete získať aj nejaké body za popis.

Formát výstupu

Vypíšte \(n\) riadkov, pričom na \(i\)-tom riadku má byť hodnota \(k_i\)-tej cifry v Zajovom zošite.

Príklady

Input:

5
0
1
4
17
19

Output:

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

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