結果

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

ソースコード

diff # 

from collections import deque

def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    
    visited = [False] * (N + 1)
    queue = deque()
    queue.append((1, 1))
    visited[1] = True
    
    found = False
    while queue:
        pos, steps = queue.popleft()
        if pos == N:
            print(steps)
            found = True
            break
        steps_num = bin(pos).count('1')
        next_pos1 = pos + steps_num
        next_pos2 = pos - steps_num
        for next_pos in [next_pos1, next_pos2]:
            if 1 <= next_pos <= N and not visited[next_pos]:
                visited[next_pos] = True
                queue.append((next_pos, steps + 1))
    
    if not found:
        print(-1)

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