# UVa 10706

## Summary

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

## Explanation

Let the sequence ${\displaystyle A_{k}}$ be ${\displaystyle S_{1}S_{2}...S_{k}}$, where ${\displaystyle 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 ${\displaystyle A_{k}}$. It is not hard to write a small subroutine to compute the length of ${\displaystyle A_{k}}$. Let ${\displaystyle len(S)}$ denote the length of some sequence S and ${\displaystyle d_{k}}$ the number of digits of k. Then by noticing that ${\displaystyle len(S_{k})=len(S_{k-1})+d_{k}}$ we have ${\displaystyle 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 ${\displaystyle d_{k}}$ is bounded in this problem, it can be estimated that ${\displaystyle len(A_{k})=O(k^{2})}$. This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle S_{k}}$, the rest of the job is trivial.

## Gotchas

• Take care of the marginal cases properly (e.g., Int32.MaxValue</syntaxhighlight>).
NotesI 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/