結果

問題 No.3 ビットすごろく
ユーザー mahiro
提出日時 2020-01-11 19:41:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 142 ms / 5,000 ms
コード長 682 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 77,856 KB
最終ジャッジ日時 2024-07-01 09:36:57
合計ジャッジ時間 4,172 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq


N = int(input())
visited = [False] * (N + 1)
visited[1] = True
queue = [(1, 1)]  # (訪問するまでにかかった移動数, 現在のマス)

ans = -1
while queue:
    q = heapq.heappop(queue)
    moved, now_space = q
    if now_space == N:
        ans = moved
        break
    next_move = bin(now_space).count("1")
    forward, backward = now_space + next_move, now_space - next_move
    if forward < N + 1 and not visited[forward]:
        visited[forward] = True
        heapq.heappush(queue, (moved + 1, forward))
    if backward > 0 and not visited[backward]:
        visited[backward] = True
        heapq.heappush(queue, (moved + 1, backward))
print(ans)
0