結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2017-04-14 22:53:40 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 110 ms / 5,000 ms |
コード長 | 473 bytes |
コンパイル時間 | 38 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-07-01 08:39:46 |
合計ジャッジ時間 | 4,386 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
Syntax OK
ソースコード
def count_bits(n) if n == 0 0 else ((n & 1) == 0 ? 0 : 1) + count_bits(n >> 1) end end def f(n) inf = -1 q = [1] visited = [inf]*(N_MAX+1) visited[1] = 1 while !q.empty? curr = q.shift bits = count_bits(curr) [curr - bits, curr + bits].each{|nxt| next if !nxt.between?(1, n) next if visited[nxt] != inf visited[nxt] = visited[curr] + 1 q << nxt } end visited[n] end N_MAX = 10000 N = gets.to_i p f(N)