結果

問題 No.3 ビットすごろく
ユーザー shi-moshi-mo
提出日時 2016-03-27 22:31:36
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 412 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2024-04-10 03:56:44
合計ジャッジ時間 4,192 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
12,416 KB
testcase_01 WA -
testcase_02 AC 81 ms
12,288 KB
testcase_03 AC 88 ms
12,160 KB
testcase_04 WA -
testcase_05 AC 91 ms
12,416 KB
testcase_06 AC 86 ms
12,160 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 83 ms
12,288 KB
testcase_13 AC 79 ms
12,160 KB
testcase_14 AC 85 ms
12,288 KB
testcase_15 AC 89 ms
12,416 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 75 ms
12,160 KB
testcase_22 AC 87 ms
12,160 KB
testcase_23 AC 90 ms
12,288 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 80 ms
12,160 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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)
  $nmoves[fwd] = $nmoves[i] + 1 if fwd <= n

  back = i - bitcount(i)
  return if (back < 1) || $nmoves[back]
  $nmoves[back] = $nmoves[i] + 1
  move_from(back, n)
end

$nmoves[1] = 1
1.upto(n-1) do |i|
  move_from(i, n)
end
puts $nmoves[n] || -1
0