main.ml (1720B)
1 (* 2 3 - n lighthouses 4 - each night each has a different number 5 - if a lighthouse shows x tonight, then tomorrow night it shows the sum of the squares of the decimal digits of x 6 - 24 7 - 2**2 + 4**2 8 - two lighthouses i and j are in tune if there exists a night after which, forever, both of them show exactly the same number on every single night. 9 - Kia asks: how many pairs (i,j) with i<j are in tune 10 11 7 4 16 4 2 12 13 steps: 14 15 0 - 7 4 16 4 2 16 1 - 49 16 37 16 4 17 2 - 97 37 58 37 16 18 3 - 130 58 89 58 37 19 4 - 10 20 21 22 1 7 10 100 23 24 4 16 37 25 26 2 20 4 27 28 can I just simulate these 29 30 - : int -> (int -> 'a) -> 'a array = <fun> 31 32 *) 33 34 let readInt () = Scanf.scanf " %d" (fun x -> x) 35 36 let rec nextStep num = 37 if num = 0 then 0 else ((num mod 10)*(num mod 10)) + (nextStep (num / 10)) 38 39 let rec simulate arr steps = 40 if steps = 0 then arr else 41 let nxt = Array.map nextStep arr in simulate nxt (steps-1) 42 43 let score arr = 44 let tbl = Hashtbl.create 100 in 45 let rec acc idx running = 46 if idx = Array.length arr then running 47 else match (try Some (Hashtbl.find tbl arr.(idx)) with Not_found -> None) with 48 | Some x -> (Hashtbl.replace tbl arr.(idx) (x+1); acc (idx+1) (running+x)) 49 | None -> (Hashtbl.add tbl arr.(idx) 1; acc (idx+1) (running)) 50 in acc 0 0 51 52 53 let testCase () = 54 let nums = readInt () in 55 let arr = Array.init nums (fun _ -> readInt ()) 56 in print_int (score (simulate arr 1000)); print_newline () 57 58 let () = 59 let testCases = readInt () in 60 let rec acc idx = 61 if idx = testCases then () else (testCase (); acc (idx+1)) 62 in acc 0 63 64 65 (* I have proven collatz conjuecture, just run a bunch of steps *)