結果
問題 |
No.2241 Reach 1
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:59:11 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,661 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,856 KB |
実行使用メモリ | 59,324 KB |
最終ジャッジ日時 | 2025-04-16 01:00:25 |
合計ジャッジ時間 | 2,215 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 18 |
ソースコード
import heapq def divide_by_2(m): k = 0 while m % 2 == 0: m = m // 2 k += 1 return m, k def pow_mod(s, mod): if mod == 0: return 0 result = 1 base = 2 % mod while s > 0: if s % 2 == 1: result = (result * base) % mod base = (base * base) % mod s = s // 2 return result def solve(N): max_s = 20 # sの上限を設定 heap = [] heapq.heappush(heap, (0, N)) visited = {N: 0} while heap: steps, m = heapq.heappop(heap) if m == 1: return steps if steps > visited.get(m, float('inf')): continue # 操作1を適用 m_new, k = divide_by_2(m) new_steps = steps + 1 if m_new not in visited or new_steps < visited[m_new]: visited[m_new] = new_steps heapq.heappush(heap, (new_steps, m_new)) # 操作2を適用(mが奇数の場合のみ) if m % 2 == 1: # 候補1: k=1 new_m = m * 1 + 1 m_div, s = divide_by_2(new_m) new_steps_2 = steps + 2 if m_div not in visited or new_steps_2 < visited.get(m_div, float('inf')): if m_div in visited: if new_steps_2 < visited[m_div]: visited[m_div] = new_steps_2 heapq.heappush(heap, (new_steps_2, m_div)) else: visited[m_div] = new_steps_2 heapq.heappush(heap, (new_steps_2, m_div)) # 候補2: sを1からmax_sまで試す for s_candidate in range(1, max_s + 1): mod = m pow_2s = pow_mod(s_candidate, mod) if pow_2s == 1 % mod: numerator = (1 << s_candidate) - 1 if numerator % mod == 0: k_candidate = numerator // mod if k_candidate > 0: new_steps_2 = steps + 2 if 1 not in visited or new_steps_2 < visited.get(1, float('inf')): if 1 in visited: if new_steps_2 < visited[1]: visited[1] = new_steps_2 heapq.heappush(heap, (new_steps_2, 1)) else: visited[1] = new_steps_2 heapq.heappush(heap, (new_steps_2, 1)) return -1 # 問題文より到達しない N = int(input()) print(solve(N))