# UVa 10706

##  Summary

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

##  Explanation

Let the sequence Ak be S1S2...Sk, where Sk consists of positive integer numbers ranging from 1 to k. A natural question is, what is the length or the number of digits of Ak. It is not hard to write a small subroutine to compute the length of Ak. Let len(S) denote the length of some sequence S and dk the number of digits of k. Then by noticing that len(Sk) = len(Sk - 1) + dk 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 dk is bounded in this problem, it can be estimated that len(Ak) = O(k2). This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually len(A31267) < 2,147,483,647 < len(A31268). 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 Sk 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 Sk, 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/ 
 Retrieved from "http://www.algorithmist.com/index.php?title=UVa_10706&oldid=13340" Category: UVa Online Judge 
 
 Personal tools Log in / create account Namespaces Page Discussion Variants Views Read Edit View history Actions Search Navigation Main Page Programming Contest Calendar UVa Sphere Online Judge Recent changes Random page Help Toolbox What links here Related changes Special pages Printable version Permanent link This page was last modified on 28 March 2013, at 06:55. This page has been accessed 3,687 times. Content is available under GNU Free Documentation License 1.2. Privacy policy About Algorithmist Disclaimers if ( window.isMSIE55 ) fixalpha(); if(window.mw){ mw.loader.load(["mediawiki.user", "mediawiki.util", "mediawiki.page.ready", "mediawiki.legacy.wikibits", "mediawiki.legacy.ajax", "mediawiki.legacy.mwsuggest"]); } if(window.mw){ mw.user.options.set({"ccmeonemails":0,"cols":80,"date":"default","diffonly":0,"disablemail":0,"disablesuggest":0,"editfont":"default","editondblclick":0,"editsection":1,"editsectiononrightclick":0,"enotifminoredits":0,"enotifrevealaddr":0,"enotifusertalkpages":1,"enotifwatchlistpages":0,"extendwatchlist":0,"externaldiff":0,"externaleditor":0,"fancysig":0,"forceeditsummary":0,"gender":"unknown","hideminor":0,"hidepatrolled":0,"highlightbroken":1,"imagesize":2,"justify":0,"math":1,"minordefault":0,"newpageshidepatrolled":0,"nocache":0,"noconvertlink":0,"norollbackdiff":0,"numberheadings":0,"previewonfirst":0,"previewontop":1,"quickbar":5,"rcdays":7,"rclimit":50,"rememberpassword":0,"rows":25,"searchlimit":20,"showhiddencats":0,"showjumplinks":1,"shownumberswatching":1,"showtoc":1,"showtoolbar":1,"skin":"vector","stubthreshold":0,"thumbsize":2,"underline":2,"uselivepreview":0,"usenewrc":0,"watchcreations":0,"watchdefault":0,"watchdeletion":0,"watchlistdays":3,"watchlisthideanons":0, "watchlisthidebots":0,"watchlisthideliu":0,"watchlisthideminor":0,"watchlisthideown":0,"watchlisthidepatrolled":0,"watchmoves":0,"wllimit":250,"variant":"en","language":"en","searchNs0":true,"searchNs1":false,"searchNs2":false,"searchNs3":false,"searchNs4":false,"searchNs5":false,"searchNs6":false,"searchNs7":false,"searchNs8":false,"searchNs9":false,"searchNs10":false,"searchNs11":false,"searchNs12":false,"searchNs13":false,"searchNs14":false,"searchNs15":false});;mw.user.tokens.set({"editToken":"+\\","watchToken":false});;mw.loader.state({"user.options":"ready","user.tokens":"ready"}); /* cache key: wikidb:resourceloader:filter:minify-js:4:19a4b18a9ac79a6b8c60b24af4668814 */ }