main.ml (1799B)
1 (* 2 - given n: 3 - create arr [1,2,...,n] 4 - compute the sum across all digits in the elements 5 - 11 -> 1 + 1 -> 2 6 7 - hmm, could I just... precompute before even fucking asking? 8 - nope, 64kb max size 9 10 - after we read in all of our problems, we generate a table for each value from 0 -> upper bound 11 - we then do lookups per subsequent query 12 13 - alt. idea: 14 - have a lookup table for each of our queries and be intelligent about which results to cache 15 - nah, these can be up to 1000 while the total size is up to 10k, only 10x higher, probably fine 16 *) 17 18 let read_int () = 19 Scanf.scanf("%d\n") (fun x -> x) 20 in 21 22 (* returns largest *) 23 24 let readInputs arr = 25 let rec acc idx = 26 if idx >= (Array.length arr) 27 then -1 28 else let cn = read_int() in 29 let () = arr.(idx) <- cn in 30 let pr = acc (idx + 1) in 31 if cn > pr then cn else pr 32 in acc 0 33 in 34 35 let rec sumDigits idx = 36 let base = (idx mod 10) in 37 if idx >= 10 then 38 base + sumDigits (idx / 10) 39 else 40 base 41 in 42 43 let preComputeTo arr = 44 let rec acc running idx = 45 if idx = Array.length arr 46 then () 47 else (let updated = (running + (sumDigits idx)) in arr.(idx) <- updated; acc updated (idx+1)) 48 in acc 0 0 49 in 50 51 let printAnswer cases preComp = 52 let rec acc idx = 53 if idx >= Array.length cases then () else (print_int preComp.(cases.(idx)); print_newline (); acc (idx+1)) 54 in acc 0 55 in 56 57 58 let testCases = read_int () in 59 let cases = Array.make (testCases) 0 in 60 let maxVal = readInputs cases in 61 let preComp = Array.make (maxVal+1) 0 in 62 let () = preComputeTo preComp in 63 printAnswer cases preComp