結果

問題 No.3 ビットすごろく
ユーザー otsuneko
提出日時 2021-04-24 19:44:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 66 ms / 5,000 ms
コード長 573 bytes
コンパイル時間 589 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 68,992 KB
最終ジャッジ日時 2024-07-04 09:11:50
合計ジャッジ時間 3,572 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque

def bfs():
    queue = deque()
    queue.append(1)
    nums = [0]*N
    nums[0] = 1
    while queue:
        n = queue.popleft()
        if n == N:
            return nums[n-1]
        move = format(n,"b").count("1")
        if 1 <= n-move <= N and nums[n-move-1] == 0:
            queue.append(n-move)
            nums[n-move-1] += nums[n-1] + 1
        if 1 <= n+move <= N and nums[n+move-1] == 0:
            queue.append(n+move)
            nums[n+move-1] += nums[n-1] + 1
    return -1

N = int(input())
print(bfs())
0