結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2016-06-12 12:17:21 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 102 ms / 5,000 ms |
コード長 | 659 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-01 07:59:32 |
合計ジャッジ時間 | 4,305 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
Syntax OK
ソースコード
INF = 10000000000 def sum_of_1 n sum = 0 while n > 0 do sum += n % 2 n /= 2 end return sum end n = gets.to_i if n === 1 puts 1 exit end dist = {} (n+1).times {|i| dist[i] = INF } queue = Queue.new queue.push(1) dist[1] = 1 while true do if queue.size == 0 break end val = queue.pop() diff = sum_of_1 val right = val + diff left = val - diff if right === n || left === n puts (dist[val] + 1) exit end if right < n && dist[right] == INF dist[right] = dist[val] + 1 queue.push(right) end if left > 0 && dist[left] == INF dist[left] = dist[val] + 1 queue.push(left) end end puts(-1)