結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2025-03-26 15:43:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 1,178 bytes |
コンパイル時間 | 399 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 69,632 KB |
最終ジャッジ日時 | 2025-03-26 15:43:38 |
合計ジャッジ時間 | 2,955 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque n = int(input()) if n == 1: print(1) exit() visited = [float('inf')] * (n + 1) visited[1] = 1 q = deque() q.append((1, 1)) answer = -1 found = False while q: pos, steps = q.popleft() # Check if current position is the target if pos == n: answer = steps found = True break # Calculate the number of 1 bits in the current position bit_count = bin(pos).count('1') # Explore both forward and backward moves for delta in [bit_count, -bit_count]: next_pos = pos + delta # Check if the next position is within bounds if 1 <= next_pos <= n: # If next position is the target, update answer and break if next_pos == n: answer = steps + 1 found = True q = deque() # Clear the queue to exit the loop break # Update the visited array and enqueue if a shorter path is found if visited[next_pos] > steps + 1: visited[next_pos] = steps + 1 q.append((next_pos, steps + 1)) if found: break print(answer if found else -1)