結果
問題 |
No.4 おもりと天秤
|
ユーザー |
![]() |
提出日時 | 2017-08-18 10:59:14 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 675 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 21,576 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-09 00:27:08 |
合計ジャッジ時間 | 1,222 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
let solve w n m = let z = m / 2 in let s = Array.make (z + 1) false in s.(0) <- true; let t = Array.copy s in let rec doit i = if i = n then t.(z) else begin for x = w.(i) to z do t.(x) <- s.(x) || s.(x - w.(i)) done; if t.(z) then true else begin Array.iteri (fun i e -> s.(i) <- e) t; doit (i + 1) end end in doit 0 let read () = Scanf.scanf "%d " (fun i -> i) let () = let n = read () in let w = Array.init n (fun _ -> read ()) in let m = Array.fold_left (+) 0 w in if m mod 2 = 1 then print_endline "impossible" else print_endline (if solve w n m then "possible" else "impossible")