#P17811. [ICPC 2019 Nanchang R] Powers of Two
[ICPC 2019 Nanchang R] Powers of Two
Problem Description
Andrew has noticed that and are quite unusual digits. There are small powers of two that start with in decimal notation (), with (), ..., with (), and with (). However, the smallest power of that starts with in decimal notation is the enormous , and the smallest power of that starts with is even bigger: .
Having learned this, Andrew wants to study the powers of two a bit more. More precisely, he will generate a number and present a positive integer , and ask you: what is the -th smallest power of two that starts with in decimal notation?
Prepare for answering such requests! Note that it's possible to prove that there exist arbitrarily many powers of two that start with any given prefix.
Input Format
The input will contain one positive integer with at most digits without leading zeroes, and a positive integer up to .
Output Format
Output the -th smallest non-negative integer such that starts with in decimal notation.
123 1
90
123 12345
3510491
1234567890000000000 67891
192992076478480096905880
Hint
To solve this problem, you may need the logarithm of to the base of the mathematical constant . Here it is in decimal notation with decimal places after the decimal point:
:::align{center}
:::