algorithms

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

main.ml (1232B)


      1 let readInt () =
      2     Scanf.scanf " %d" (fun x->x)
      3 
      4 let loadArr arr arrLen =
      5     let rec acc idx =
      6         if idx = arrLen then ()
      7         else (arr.(idx) <- readInt (); acc (idx + 1))
      8     in acc 0
      9 
     10 let solve arr k =
     11     let n = Array.length arr in
     12     let rec acc minIdx turn target acMexA acMexB =
     13         if minIdx = n || arr.(minIdx) > target then
     14             if acMexA >= k && acMexB >= k
     15                 then acc minIdx turn (target + 1) 0 0
     16                 else (acMexA >= k) <> (acMexB >= k)
     17         else if acMexA >= k && acMexB >= k then
     18             acc (minIdx + 1) turn target acMexA acMexB
     19         else if turn then
     20             acc (minIdx + 1) false target (acMexA + 1) acMexB
     21         else
     22             acc (minIdx + 1) true target acMexA (acMexB + 1)
     23     in acc 0 true 0 0 0
     24 
     25 let handleTestCase () =
     26     let arrLen = readInt () in
     27     let k = readInt () in
     28     let arr = Array.make arrLen 0 in
     29     let () = loadArr arr arrLen in
     30     let () = Array.sort compare arr in
     31     let soln = solve arr k in
     32     if soln then print_endline "YES" else print_endline "NO"
     33 
     34 let () =
     35     let testCases = readInt () in
     36     let rec acc idx =
     37         if idx = testCases then ()
     38         else (handleTestCase (); acc (idx+1))
     39     in acc 0