algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.ml (876B)


      1 let readInput () = 
      2     Scanf.scanf " %d %d" (fun a b -> (a,b))
      3 in
      4 
      5 let rec readList take = 
      6     if take <= 0 then []
      7     else 
      8         let x = Scanf.scanf " %d" (fun a -> a)
      9             in x :: readList (take-1)
     10 in
     11 
     12 let append ls input = 
     13     match ls with 
     14     | [] -> [input]
     15     | h :: _ -> (h + input) :: ls
     16 in
     17 
     18 let prefixSum ls = 
     19     List.rev (List.fold_left append [0] ls)
     20 in
     21 
     22 let rec minSum i leftLs rightLs = 
     23     match rightLs with
     24     | [] -> (max_int, 0)
     25     | h :: t -> min (h - (List.hd leftLs), i) (minSum (i + 1) (List.tl leftLs) (List.tl rightLs))
     26 in
     27 
     28 (* their compiler is old as shit *)
     29 let rec drop n ls =
     30     match ls with
     31     | _ :: t when n > 0 -> drop (n - 1) t
     32     | _ -> ls
     33 in
     34 
     35 let ll, take = readInput () in 
     36     let ls = readList ll in 
     37         let pre = prefixSum ls in
     38             print_int (snd (minSum 1 pre (drop take pre))); print_newline ()