UVa 10706

From Algorithmist
Jump to navigation Jump to search

10706 - Number Sequence[edit]

Summary[edit]

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

Explanation[edit]

Let the sequence be , where consists of positive integer numbers ranging from 1 to k. A natural question is, what is the length or the number of digits of . It is not hard to write a small subroutine to compute the length of . Let denote the length of some sequence S and the number of digits of k. Then by noticing that we have . Since is bounded in this problem, it can be estimated that . This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually . 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 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 , the rest of the job is trivial.

Gotchas[edit]

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

Notes[edit]

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

Input[edit]

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

Output[edit]

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

Solution[edit]