fork(14) download
copy 
  1. (*
  2.  * UVa 10706. Number Sequence
  3.  * 
  4.  * http://u...content-available-to-author-only...e.org/external/107/10706.html
  5.  *)
  6. open System
  7.  
  8. let mutable numLength= 1
  9. (*
  10.  * :numbers:[int] -> length_each_num:[int]
  11.  *)
  12. let getNumLengths (l:int list) :int list = 
  13.   (*
  14.    * :num:Int -> numLength:Int 
  15.    *)
  16.   let computeLength (i:int):int =
  17.     let rec computeLength' (i:int) (l:int) :int = 
  18.       if ((i/(System.Math.Pow(10|>float,l|>float)|>int)) = 0) then 
  19.         numLength <- l
  20.         l 
  21.       else 
  22.         computeLength' i (l+1)
  23.     computeLength' i numLength
  24.  
  25.   numLength <- 1 // setting numberLength <- 1 
  26.   l
  27.   |> List.map computeLength
  28.  
  29. (* Utility function to print a sequence 
  30.  * :seq<'a> -> unit
  31.  *)
  32. let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn "" 
  33.  
  34.  
  35. let cumulativeSumofLengths l = 
  36.   let computeLengths list:int list =
  37.     let rec computeNoOfElements' l acc = 
  38.       match l with 
  39.       | [] -> []
  40.       | x::xs -> (x + acc)::(computeNoOfElements' xs (x + acc))
  41.     computeNoOfElements' list 0  
  42.   l 
  43.   |> computeLengths  
  44.   |> computeLengths 
  45.  
  46.  
  47. (*
  48.  * Performs a binary search on the cumulative sums of lengths. 
  49.  * and return a tuple as (minBound, maxBound)
  50.  * : arr: int[] -> n: int -> (int,int)
  51.  *)
  52. let getBounds a (n:int): int*int = 
  53.   let binarySearch (arr:int[]) (n:int) : (int*int) =
  54.     let rec binarySearch' (arr:int[]) (n:int)  (low:int) (high:int) = 
  55.       if arr.[high] < n then 
  56.          (high, System.Int32.MaxValue)
  57.       else if high - low <= 1 then 
  58.         if arr.[low] = n then
  59.           (low, low)
  60.         else  
  61.           (low,high)
  62.       else
  63.         let mid = (high + low)/2
  64.         match arr.[mid],n with 
  65.         |  (a,b) when a <= b->  binarySearch' arr n  mid high
  66.         |  _ ->  binarySearch' arr n  low mid
  67.     binarySearch'  arr n 0 (arr.Length-1)
  68.   binarySearch a n 
  69.  
  70. let numberAt a n = 
  71.   let getDigitAtIndex (relLength:int) (index:int): int = 
  72.     let rec getIntAtIndex' (relLength:int) (startNum:int)(endNum:int):int = 
  73.       if startNum <= endNum then 
  74.         let str = startNum.ToString()
  75.         match  relLength  - str.Length with 
  76.         | diff when diff <= 0 -> System.Int32.Parse(str.[relLength-1].ToString())
  77.         | diff                ->  getIntAtIndex'  (relLength - str.Length)  (startNum+1) endNum
  78.  
  79.       else 
  80.         -1
  81.     getIntAtIndex' relLength 1 index  
  82.   match  getBounds a n with 
  83.   | 0,0  -> 1
  84.   | l,h when h = System.Int32.MaxValue -> getDigitAtIndex (n-a.[l]) (l+1)  
  85.   | l,h when l = h -> getDigitAtIndex (n-a.[l-1]) (l+1)
  86.   | l,h            -> getDigitAtIndex (n-a.[l]) (l+2)
  87.  
  88.  
  89.  
  90. let solve_UVA10706 ()= 
  91.   let arr = 
  92.     [1..31267]
  93.     |> getNumLengths 
  94.     |> cumulativeSumofLengths 
  95.     |> List.toArray
  96.  
  97.   let T = Console.ReadLine().Trim() |> int
  98.   let mutable i:string = null
  99.  
  100.   for case_i = 1 to T do 
  101.     i <- System.Console.ReadLine()
  102.     if i <> null then 
  103.       i
  104.       |> Int32.Parse 
  105.       |> numberAt arr
  106.       |> printfn "%d"
  107.  
  108. // running script 
  109. solve_UVA10706()
  110.  
  111.  
Success #stdin #stdout 0.17s 51280KB
comments (?)
stdin
copy 
18 
8 
3 
80 
546 
23423 
65753 
2345 
45645756 
546454 
6786797 
131231 
78934124 
68904565 
123487907 
5655 
778888 
101011 
2147483647
stdout
copy 
2
2
0
2
3
1
5
5
2
5
9
7
5
7
1
5
5
2
https://ideone.com/vOCpfC
language:
F# (mono 4.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!