概要

長さ \(L\) のロープを何回か半分に折りたたんで、収納ケースの長さ \(W\) 以下にするために必要な最小の折りたたみ回数を求める問題です。

考察

問題の操作は、現在の長さ \(x\) に対して \(\lceil x/2 \rceil\) を計算することです。つまり、\(x\) が奇数の場合は \((x+1)/2\)、偶数の場合は \(x/2\) になります。

素朴なアプローチでは、実際に \(L\) から始めて \(W\) 以下になるまで折りたたみ操作を繰り返すことが考えられます。しかし、\(L\) の最大値が \(10^{18}\) と非常に大きいため、単純なループでも十分高速に動作します。なぜなら、操作を1回行うごとに値がほぼ半分になるため、必要な操作回数は最大でも約60回（\(2^{60} \approx 10^{18}\)）程度だからです。

アルゴリズム

1. 最初に \(L \leq W\) かどうかをチェックし、真ならば0を返す
2. \(L > W\) の場合、現在の長さを \(L\) で初期化し、カウンタを0に設定
3. 現在の長さが \(W\) より大きい間、以下を繰り返す：
   • 現在の長さを \(\lceil x/2 \rceil\) で更新（\((x + 1) // 2\) で計算）
   • カウンタを1増やす
4. カウンタの値を出力する

計算量

• 時間計算量: \(O(\log L)\)
  • 各操作で長さが約半分になるため、反復回数は \(\log_2 L\) 回程度
• 空間計算量: \(O(1)\)
  • 数個の変数のみを使用

実装のポイント

• 整数演算のみで処理できる（浮動小数点数は不要）

• 折りたたみ操作は \((x + 1) // 2\) で正確に表現できる

• 大きな数値（\(10^{18}\)）でも、操作回数が60回程度で済むため効率的

• 最初の条件分岐（\(L \leq W\)）を忘れないように注意

  ソースコード

def main():
    import sys
    data = sys.stdin.readline().split()
    L = int(data[0])
    W = int(data[1])
    
    if L <= W:
        print(0)
        return
        
    count = 0
    current = L
    while current > W:
        current = (current + 1) // 2
        count += 1
        
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。