V tomto vzoráku budeme zapisovať číslo ktoré dostaneme tým, že napíšeme $k>1$ za sebou idúcich čísel začínajúc číslom $a$, ako $F(a, k)$.

Našou úlohou je pre dané $n$ nájsť najmenšie číslo $x > n$ ktoré sa dá takto zostrojiť, a spraviť to pre $T$ zadaných čísel.

Ľahšie vyrobiť ako overiť

Keďže vieme vyrobiť $F(1,7) = 1234567 > 10^6$, vieme že všetky odpovede pre prvú sadu (kde $n$ nepresiahne $10^6$) bude nanajvýš toto číslo.

Prvá vec čo nám môže napadnúť je teda skúšať čísla $n+1$, $n+2$, a vždy overiť či sa dá popísaným spôsobom vyrobiť. Prvé ktoré sa naozaj aj dá bude správna odpoveď. Tento prístup síce funguje, no má dve nepríjemné vlastnosti:

• overiť či sa nejaké číslo dá vyrobiť požadovaným postupom je trochu komplikované
• odhadnúť koľko čísel musíme v najhoršiom prípade vyskúšať kým nájdeme vyrobitelné číslo je tiež trochu komplikované.

Naše odpoveďové čísla majú vlastnosť, že sa ľahšie vyrábajú ako overujú. Poďme teda všetky platné čísla do $1234567$ vyrobiť, a potom v nich ľen nájdeme pre každé $n$ najmenšie väčšie a máme hotovo.

Všimnime si, že ak začneme číslom so štyrmi ciframi, tak najmenšie číslo ktoré vieme vytvoriť bude mať osem cifier, čo už je viac ako treba. Stačí nám teda vyskúšat $F(a,k)$ kde $a \leq 999$. No a tie už hravo vieme vyskúšať všetky: pre každé $a$ od $1$ po $999$ budeme za sebou lepiť nasledujúce čísla, kým celý výsledok nepresahuje $1234567$¹.

Všetky takto vyrobené čísla si zapamätáme a usporiadame. Pre každé $n$ na vstupe potom v tomto zozname môžeme binárne vyhľadať najmenšie väčšie číslo.

Vygenerujeme s naším odhadom (vo všeobecnom prípade s hranicou inou ako $10^6$) $O(n)$ čísel, usporiadame ich, a pre každé hľadané číslo $n$ v tomto zozname binárne vyhľadáme. Naše časové zložitosti pre tieto kroky sú $O(n)$, $O(nlogn)$ a $O(Tlogn)$, dokopy teda $O((T+n)logn)$. Pamätáme si pritom naše pole čísel ktoré má veľkosť $O(n)$².

Dve veľké čísla za sebou?

Ako $n$ rastie, horeuvedenými spôsobmi budeme prikrátki. Medzery medzi číslami, ktoré vieme vyrobiť vedia byť naozaj veľké - napríklad medzi 100000000100000001 a 100000001100000002 nevieme vyrobiť žiadne vyhovujúce čísla. Pre druhý prístup, v ktorom ich skúšame generovať, máme okolo $10^9$ kandidátov pre začiatočné číslo $a$. To nestiháme.

Skúsme teda využiť podmienku, že stačí aby sme sa pozreli na čísla ktoré získame nalepením práve dvoch za sebou idúcich čísel. Pozrime sa na dve rôzne také čísla, $x = F(a,2)$ a $y = F(b,2)$ kde BÚNV $b>a$. Ak má $b$ viac cifier ako $a$ (alebo $b+1$ viac ako $a+1$) vytvoríme číslo s viac ciframi, a $y$ bude teda väčšie. Ak majú $a,a+1, b, b+1$ rovnako veľa cifier, vyrobíme čísla rovnakej dĺžky, pričom $x$ sa začína ciframi čísla $a$ a $y$ ciframi čísla $b$. Keďže $b>a$, tak nutne aj $y>x$. Inými slovami: keď máme dve čísla získané zlepením práve dvoch za sebou idúcich čísel, tak čím väčším číslom začneme, tým väčšie číslo nakoniec vyrobíme. $F(a, 2)$ je rastúca funkcia v závislosti od $a$. To znamená že odpoveď vieme binárne vyhľadať: stačí nám len nájsť to číslo $a$, pre ktoré už $F(a, 2) > n$.

Vieme že musíme začať aspoň číslom $1$ a najviac číslom polovičnej dĺžky ako $n$, teda číslom veľkosti $O(\sqrt(n))$³.

Pre každé skúšanie počas binárneho vyhľadávania v logaritmickom čase zlepíme dve čísla dokopy a porovnáme ich s $n$.

Časová zložitosť je $O(T log(n)^2)$⁴, a pamäťová $O(1)$.

No a čo keď ich je viac

No a nakoniec nám stačí tento prístup trochu zovšeobecniť. Pre ľubovoľne zvolené $k>2$ je funkcia $F(a, k)$ rastúca v závislosti od $a$.

Pre každé číslo na vstupe teda vyskúšame všetky možnosti, koľko čísel chceme zlepiť dokopy, od $k=2$ po $k=$ dĺžka $n$, čiže $logn$. V našom prípade pre $n=10^{18}$ je teda horná hranica napríklad $k=19$.

Pre každú z týchto možností $k$ binárne vyhľadáme najmenšie $a$ pre ktoré $F(a,k) > n$, a zo všetkých takto nájdeních odpovedí si zapamätáme a vypíšeme tú najmenšiu.

Dávajte si pritom v jazykoch s obmedzenou veľkosťou čísel dobrý pozor aby vám pri vytváraní/porovnávaní nepretieklo $F(a,k)$.

Pamäťová zložitosť sa nám nemení a ostáva $O(1)$. Časovú zložitosť sme si zhoršili o skúšania všetkých $k$, ktorých je $O(logn)$, bude teda $O(T log(n)^3)$.