結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2016-03-27 23:03:21 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 141 ms / 5,000 ms |
コード長 | 577 bytes |
コンパイル時間 | 42 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-07-01 07:48:20 |
合計ジャッジ時間 | 4,735 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
Syntax OK
ソースコード
n = gets.to_i $nmoves = [] $bc = [] def bitcount(i) $bc[i] ||= i.to_s(2).count('1') end def move_from(i, n) return unless $nmoves[i] fwd = i + bitcount(i) if fwd <= n n_fwd = $nmoves[i] + 1 if $nmoves[fwd].nil? || n_fwd < $nmoves[fwd] $nmoves[fwd] = n_fwd move_from(fwd, n) end end back = i - bitcount(i) return if back < 1 n_back = $nmoves[i] + 1 return if $nmoves[back] && $nmoves[back] <= n_back $nmoves[back] = n_back move_from(back, n) end $nmoves[1] = 1 1.upto(n-1) do |i| move_from(i, n) end puts $nmoves[n] || -1