結果

問題 No.3 ビットすごろく
コンテスト
ユーザー shin
提出日時 2022-10-10 16:27:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 596 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-06-24 10:37:25
合計ジャッジ時間 2,520 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ビットすごろく

N = int(input())

root = list(0 for i in range(N+1))

root[1] = 1
stack = [1]

while len(stack) > 0:
    s = stack.pop(0)
    a = s + s.bit_count()
    b = s - s.bit_count()
    #print(a , b)
    
    
    if a <= N and (root[a] == 0 or root[a] > root[s] + 1):
        root[a] = root[s] + 1
        stack.append(a)
    
    if b == 0:
        #print(root , stack)
        continue
    elif root[b] == 0 or root[b] > root[s] + 1:
        root[b] = root[s] + 1
        stack.append(b)
    
    #print(root , stack)

if root[N] == 0:
        root[N] = -1

print(root[N])
0