結果

問題 No.2241 Reach 1
ユーザー lam6er
提出日時 2025-03-20 18:48:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,654 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 56,048 KB
最終ジャッジ日時 2025-03-20 18:49:46
合計ジャッジ時間 2,754 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    N = int(input())
    
    # Step 1: Convert N to an odd number by dividing by 2 as much as possible
    m_init = N
    steps_init = 0
    if m_init % 2 == 0:
        steps_init = 1
        while m_init % 2 == 0:
            m_init //= 2
    
    # Early exit if m_init is 1
    if m_init == 1:
        print(steps_init)
        return
    
    visited = set()
    q = deque()
    q.append((m_init, steps_init))
    visited.add(m_init)
    
    while q:
        current_m, current_steps = q.popleft()
        
        if current_m == 1:
            print(current_steps)
            return
        
        # Candidate 1: k=1
        new_val = current_m * 1 + 1
        new_m = new_val
        while new_m % 2 == 0:
            new_m //= 2
        new_steps = current_steps + 2
        if new_m not in visited:
            visited.add(new_m)
            q.append((new_m, new_steps))
        
        # Other candidates: find s where 2^s -1 is divisible by current_m
        for s in range(1, 31):
            power = 1 << s  # 2^s
            required = power - 1
            if required % current_m == 0:
                k = required // current_m
                if k <= 0:
                    continue
                # new_val_c should be power, divided to 1
                new_m_c = 1
                new_steps_c = current_steps + 2
                if new_m_c not in visited:
                    visited.add(new_m_c)
                    q.append((new_m_c, new_steps_c))
    
    # This is just a fallback; the problem states the solution always exists
    print(-1)

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