C - Zbierka

Pán Pterodaktylos je zberateľom. Vášnivým a takpovediac univerzálnym. Zbiera úplne všetko: známky, motýle, známky s obrázkami motýľov, ba dokonca aj všetky nezáporné celé čísla. Z tých má niekoľko zvlášť vydarených zbierok. Každá zbierka čísel je určená parametrami B a D a obsahuje všetky nezáporné celé čísla, ktoré sa dajú zapísať v sústave so základom B pomocou najviac D číslic. Pripomeňme, že zápis x_k-1...x₀, x_i∈{0,...,B-1}, v sústave so základom B predstavuje číslo Σ_i=0^k-1 x_i B_i. Tieto čísla sú v zbierke zoradené dômyselným spôsobom: najprv vzostupne podľa svojho ciferného súčtu a v rámci skupiny s rovnakým ciferným súčtom vzostupne podľa hodnoty čísel. Napríklad zbierka označená parametrami B=3, D=2 obsahuje najviac dvojciferná čísla v trojkovej sústave, a to v nasledujúcom poradí: 0; 1, 10; 2, 11, 20; 12, 21; 22 (bodkočiarkou sú oddelené bloky čísel s rovnakým ciferným súčtom). Pre väčšie hodnoty B a D je takáto zbierka veľmi rozsiahla. Ak pán Pterodaktylos chce zo zbierky vybrať k-té číslo v poradí, čaká ho zvyčajne dlhá cesta medzi kilometrami regálov, kým sa k nemu dostane. Určite Vám napadlo, že to vôbec nie je potrebné – ak viete, že zbierka obsahuje skutočne všetky čísla, dá sa k-té číslo v poradí ľahko spočítať.

Úloha

Vstup

Výstup

Príklad 1

Vstup:

3 2 5

Výstup:

11

Vysvetlenie:

Príklad 2

Vstup:

10 15 999999999999998

Výstup:

999999999999989