Overview

Given a rope of length \(L\), we repeatedly fold it in half (the length becomes \(\lceil x/2\rceil\) after each fold) and find the minimum number of folds needed to make the length \(W\) or less.

Analysis

The key observation is that “each fold roughly halves the length.” In other words, the length decreases very rapidly.

• After one fold, a length of \(x\) becomes \(\lceil x/2\rceil\).
  • For example, if \(x=7\), then \(\lceil 7/2\rceil=4\)
  • If \(x=8\), then \(\lceil 8/2\rceil=4\)
• Therefore, we just keep folding as long as \(L>W\), and the number of folds performed is exactly the minimum number.
  • Why is it minimal: There is no way to reduce the length other than folding, and as long as \(L>W\), at least one more fold is necessary. Thus, the number of folds performed until the condition is met is the minimum.

Although the constraints are large with \(L,W \le 10^{18}\), since the length roughly halves with each fold, the number of iterations is at most \(O(\log L)\). Therefore, a simple loop is fast enough.

Concrete example: - \(L=10, W=3\) - \(10 \to \lceil 10/2\rceil=5\) (1 fold) - \(5 \to \lceil 5/2\rceil=3\) (2 folds) - \(3 \le 3\), so the answer is 2

Algorithm

1. Initialize ans=0.
2. While \(L>W\), repeat the following:
   • Update \(L \leftarrow \lceil L/2\rceil\)
   • ans += 1
3. Output ans.

\(\lceil L/2\rceil\) can be written in integer arithmetic as (L+1)//2 (ceiling division by 2).

Complexity

• Time complexity: \(O(\log L)\) (since the length roughly halves with each fold)
• Space complexity: \(O(1)\)

Implementation Notes

• Ceiling division should be written as L = (L + 1) // 2 (using L//2 would floor the result for odd numbers, which does not match the problem statement).

• When \(L \le W\), the loop is never entered, so 0 is output directly.

  Source Code

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

This editorial was generated by gpt-5.2-high.