結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2019-03-01 12:24:16 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,417 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 19,916 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-09 00:33:51 |
合計ジャッジ時間 | 1,530 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
let get arr i = arr.(i-1) let set arr i v = arr.(i-1) <- v let rec value_of_cell n acc = if n = 0 then acc else value_of_cell (n / 2) (acc + (n mod 2)) let value_of_cell n = value_of_cell n 0 let gen_graph n = let g = Array.make n [] in for i = 1 to n do let v = value_of_cell i in if i+v <= n then set g (i+v) (i::(get g (i+v))); if 1 <= i-v then set g (i-v) (i::(get g (i-v))) done; g let print_list pr ls = let rec inner = function | [] -> () | l::[] -> pr l | l::ls -> (pr l); print_string ", "; inner ls in print_string "["; inner ls; print_string "]" let print_nodes nodes = print_list (print_int) @@ Array.to_list nodes let bfs n graph nodes = let q = Queue.create () in Queue.push n q; let rec inner () = if Queue.is_empty q then (-1) else begin let v = Queue.pop q in if v = 1 then get nodes v else begin List.iter (fun l -> if get nodes l = (-1) || get nodes l > (get nodes v) + 1 then (Queue.push l q; set nodes l ((get nodes v) + 1))) (get graph v); (* print_nodes nodes; print_string "\n";*) inner () end end in inner () let solve n = let nodes = Array.make n (-1) in set nodes n 1; let g = gen_graph n in print_int @@ bfs n g nodes let _ = let n = int_of_string @@ read_line() in solve n