結果

問題 No.2241 Reach 1
コンテスト
ユーザー lam6er
提出日時 2025-04-16 01:03:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,360 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 81,332 KB
実行使用メモリ 60,772 KB
最終ジャッジ日時 2025-04-16 01:05:46
合計ジャッジ時間 2,753 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
0