UVa 10706

10706 - Number Sequence

• http://acm.uva.es/p/v107/10706.html

Summary

This problem involves a little bit of number theory and can be solved using binary search.

Explanation

Let the sequence A_k be S₁S₂...S_k, where S_k consists of positive integer numbers ranging from 1 to k. A natural question is, what is the length or the number of digits of A_k. It is not hard to write a small subroutine to compute the length of A_k. Let len(S) denote the length of some sequence S and d_k the number of digits of k. Then by noticing that len(S_k) = len(S_{k - 1}) + d_k we have $len(A_k) - len(A_{k-1}) = len(S_k) = len(S_{k-1}) + d_k = len(S_{k-2}) + d_{k-1} + d_k = ... = len(S_1) + \sum_{i=2}^k d_k$. Since d_k is bounded in this problem, it can be estimated that len(A_k) = O(k²). This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually len(A₃₁₂₆₇) < 2,147,483,647 < len(A₃₁₂₆₈). With the knowledge of the maximum k value, given the index i of a certain digit, we can use the binary search to locate the S_k to which the digit belong. This technique is similar to the one used in quick sort and thus the details are ignored. After locating the S_k, the rest of the job is trivial.

Gotchas

• Take care of the marginal cases properly (e.g., Int32.MaxValue).

Notes

• I believe that there exist more elegant ways to solve this problem.

Input

18 
8 
3 
80 
546 
23423 
65753 
2345 
45645756 
546454 
6786797 
131231 
78934124 
68904565 
123487907 
5655 
778888 
101011 
2147483647

Output

2 
2 
0 
2 
3 
1 
5 
5 
2 
5 
9 
7 
5 
7 
1 
5 
5 
2

Solution

• http://adilakhter.wordpress.com/2013/03/28/uva-10706-number-sequence-with-f/