結果

問題 No.3 ビットすごろく
コンテスト
ユーザー haccha
提出日時 2023-06-22 19:14:28
言語 Ruby
(3.4.1)
結果
AC  
実行時間 190 ms / 5,000 ms
コード長 348 bytes
コンパイル時間 50 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2024-06-30 01:44:37
合計ジャッジ時間 5,462 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

$N = gets.to_i
$steps = Array.new($N, -1)

def popcount(n)
  n.digits(2).sum
end

def carol(n, curSteps)
  return if n <= 0 || n > $N

  if $steps[n-1] == -1 || $steps[n-1] > curSteps
     $steps[n-1] = curSteps
     counts = popcount(n)
     carol(n + counts, curSteps+1)
     carol(n - counts, curSteps+1)
  end
end

carol(1, 1)
puts $steps[$N-1]
0