概要

ロープの長さ \(L\) を、半分に折る操作（長さが \(\lceil x/2\rceil\) になる）を何回か繰り返して、\(W\) 以下にするための最小回数を求めます。

考察

重要な観察は「折るたびに長さがほぼ半分になる」ことです。つまり、長さは急速に小さくなります。

• 1回折ると、長さ \(x\) は \(\lceil x/2\rceil\) になります。
  • 例えば \(x=7\) なら \(\lceil 7/2\rceil=4\)
  • \(x=8\) なら \(\lceil 8/2\rceil=4\)
• よって、\(L>W\) の間だけ折り続ければよく、折った回数がそのまま最小回数になります。
  • なぜ最小か：折る操作以外に長さを減らす方法がなく、\(L>W\) の間は必ず1回以上折る必要があるため、条件を満たすまで折った回数が最小です。

制約は \(L,W \le 10^{18}\) と大きいですが、折るたびに長さが半分程度になるので、繰り返し回数は高々 \(O(\log L)\) 回です。したがって単純なループでも十分高速です。

具体例： - \(L=10, W=3\) - \(10 \to \lceil 10/2\rceil=5\)（1回） - \(5 \to \lceil 5/2\rceil=3\)（2回） - \(3 \le 3\) になったので答えは 2

アルゴリズム

1. 回数 ans=0 とする。
2. \(L>W\) の間、次を繰り返す：
   • \(L \leftarrow \lceil L/2\rceil\) に更新する
   • ans += 1
3. ans を出力する。

\(\lceil L/2\rceil\) は整数演算で (L+1)//2 と書けます（切り上げの2で割る）。

計算量

• 時間計算量: \(O(\log L)\)（折るたびに長さが半分程度になるため）
• 空間計算量: \(O(1)\)

実装のポイント

• 切り上げの割り算は L = (L + 1) // 2 とする（L//2 だと奇数のときに切り捨てになり、問題文と一致しません）。

• \(L \le W\) のときはループに入らないので、そのまま 0 が出力されます。

  ソースコード

import sys

def main():
    L, W = map(int, sys.stdin.readline().split())
    ans = 0
    while L > W:
        L = (L + 1) // 2
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。