結果

問題 No.3 ビットすごろく
ユーザー lam6er
提出日時 2025-03-31 17:28:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 56 ms / 5,000 ms
コード長 822 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 70,672 KB
最終ジャッジ日時 2025-03-31 17:28:09
合計ジャッジ時間 2,628 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    n = int(sys.stdin.readline())
    if n == 1:
        print(1)
        return

    visited = [False] * (n + 1)
    queue = deque()
    queue.append((1, 1))
    visited[1] = True

    answer = -1
    found = False

    while queue:
        current, steps = queue.popleft()
        bits = bin(current).count('1')
        for delta in [bits, -bits]:
            next_pos = current + delta
            if next_pos == n:
                answer = steps + 1
                found = True
                break
            if 1 <= next_pos < n and not visited[next_pos]:
                visited[next_pos] = True
                queue.append((next_pos, steps + 1))
        if found:
            break

    print(answer if found else -1)

if __name__ == "__main__":
    main()
0