結果
問題 |
No.2241 Reach 1
|
ユーザー |
![]() |
提出日時 | 2025-04-16 01:05:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,360 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 81,720 KB |
実行使用メモリ | 61,024 KB |
最終ジャッジ日時 | 2025-04-16 01:07:48 |
合計ジャッジ時間 | 2,570 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 18 |
ソースコード
from collections import deque def solve(N): visited = set() q = deque() q.append((N, 0)) visited.add(N) while q: m, steps = q.popleft() # Apply operation 1: divide by maximum possible 2^k m_new = m k_op1 = 0 while m_new % 2 == 0: m_new //= 2 k_op1 += 1 new_steps = steps + (1 if k_op1 > 0 else 0) if m_new == 1: return new_steps if m_new not in visited: visited.add(m_new) q.append((m_new, new_steps)) # Check if m_new is odd and not 1 if m_new % 2 == 1 and m_new != 1: found_s = None for s in range(1, 61): # Check s from 1 to 60 power = (1 << s) - 1 if power % m_new == 0: k = power // m_new if k > 0: found_s = s break if found_s is not None: return new_steps + 2 else: next_m = m_new + 1 if next_m not in visited: visited.add(next_m) q.append((next_m, new_steps + 1)) return -1 # This line is theoretically unreachable # Read input and output the result N = int(input()) print(solve(N))