結果

問題 No.3 ビットすごろく
ユーザー irumo8202
提出日時 2022-01-21 15:22:12
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 41 ms / 5,000 ms
コード長 542 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-11-25 10:59:07
合計ジャッジ時間 2,431 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque

n = int(input())

visited = [False] * (n + 1)
visited[:1] = [True, True]
cost = [-1] * (n + 1)
cost[1] = 1
que = deque([1])

while que:
    v = que.pop()

    m = bin(v).count("1")

    if v - m >= 1:
        if not visited[v - m]:
            visited[v - m] = True
            cost[v - m] = cost[v] + 1
            que.appendleft(v - m)

    if v + m <= n:
        if not visited[v + m]:
            visited[v + m] = True
            cost[v + m] = cost[v] + 1
            que.appendleft(v + m)

print(cost[n])
0