Internet Problem Solving Contest

• Correct output for T1
• Correct output for T2
• Python 3 program solving both subproblems

The easy subtask can be solved by brute force: generate house numbers starting from 1, for each of them count the digits used and terminate once you don’t have enough digits to build the current number.

For the hard subtask this solution would be too slow. How can we improve it? The key is to notice that the answer is monotonous: if we have enough digits for houses 1 through x, we have enough digits for houses 1 through y, for any y < x. This makes it possible to determine the optimal answer using binary search.

In order to perform the binary search we have to implement a function that takes an n and verifies whether the box contains enough digits to produce numbers from 1 to n. This function will somehow count the digits used in the numbers from 1 to n and compare those counts to the counts of digits in our box.

We will now show how to calculate the value C_d, n: the number of times the digit d occurs in the numbers 0 through n − 1. The value C_d, n can easily be computed recursively in O(logn) time as follows:

• If n = 0 then C_d, 0 = 0.
• If $n \bmod 10 \not= 0$, then C_d, n is C_{d, n − 1} + the number of times d occurs in n − 1.
• If $n \bmod 10 = 0$, imagine that you listed all the numbers from 0 to n − 1.
  Look at the last digit. It cycles through 0-9 exactly n/10 times, hence you have n/10 copies of digit d there.
  Now erase the last digit. What is left? The sequence of numbers 1 through (n/10) − 1, each repeated 10 times. How many copies of your digit d are there? Obviously, for $d\not=0$ the answer is 10 ⋅ C(d, n/10).
  There is a special case with d = 0: the first 10 numbers in our list (0-9) only had a single digit each. After erasing those nothing was left (as opposed to ten 0s). Hence, for d = 0 we have to subtract those from the result: we only have 10 ⋅ (C(0, n/10) − 1) zeros among the digits other than the last digit.

Once we know how to compute the values C_d, n, we are all set. During the binary search we will compute the value C_{0, n + 1} − 1 and the values C_{1, n + 1} through C_{9, n + 1} and we will compare these to the ten values we were given as the input.