# UVa 10706

## 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_{1}S_{2}...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^{2})$ . This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually $len(A_{31267})<2,147,483,647 . 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</syntaxhighlight>).
I believe that there exist more elegant ways to solve this problem.Input18 8 3 80 546 23423 65753 2345 45645756 546454 6786797 131231 78934124 68904565 123487907 5655 778888 101011 2147483647 Output2 2 0 2 3 1 5 5 2 5 9 7 5 7 1 5 5 2 Solutionhttp://adilakhter.wordpress.com/2013/03/28/uva-10706-number-sequence-with-f/