Overview

For each ribbon, this problem uses the “quotient” and “remainder” of \(L_i\) divided by \(T_i\), and adds \(+1\) to the part count only when the remainder satisfies the condition.

Analysis

The key insight is that “there is no need to simulate the process of actually cutting \(T_i\) millimeters at a time.” For the \(i\)-th ribbon:

• First, the number of regular parts is \(\lfloor L_i / T_i \rfloor\)
• A remainder \(R_i = L_i \bmod T_i\) is left over
• If that remainder exists (\(R_i > 0\)) and is at least half (\(R_i \ge \lfloor T_i/2 \rfloor\)), then the remainder is also counted as 1 part

If we naively simulate “cutting \(T_i\) at a time,” when \(L_i\) is extremely large (e.g., \(10^{18}\)), the number of cuts could be up to \(10^{18}\), which obviously won’t finish in time (TLE). However, all we need is “how many times can we cut” and “what is the remainder,” which can be obtained in a single integer division (quotient and remainder).

Concrete examples: - When \(L=13,\,T=5\): \(13=5\times2+3\), so \(q=2, r=3\) \(\lfloor T/2 \rfloor = 2\), and since \(r=3 \ge 2\) and \(r>0\), the answer is \(2+1=3\) - When \(L=11,\,T=5\): \(q=2, r=1\) Since \(r(=1) < 2\), the answer is \(2\)

Even when \(L<T\), similarly \(q=0, r=L\), and if the remainder condition is satisfied the result is 1, otherwise 0.

Algorithm

For each ribbon \((L, T)\), do the following:

1. Compute \(q, r = \mathrm{divmod}(L, T)\) to obtain \(q=\lfloor L/T \rfloor\) (number of regular parts) and \(r=L\bmod T\) (remainder)
2. If \(r>0\) and \(r \ge \lfloor T/2 \rfloor\), then \(q \leftarrow q+1\)
3. Output \(q\)

Implementing exactly this computes \(P_i\) as defined in the problem.

Complexity

• Time complexity: \(O(N)\) (constant-time computation per ribbon)
• Space complexity: \(O(1)\) (excluding output)

Implementation Notes

• In Python, using divmod(L, T) conveniently gives the quotient and remainder simultaneously.

• The condition follows the problem statement directly: r > 0 and r >= (T // 2) (note that when \(r=0\), we do not add an extra part).

• Since \(N\) can be up to \(2\times10^5\), using sys.stdin.buffer.read() for input is faster.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    out = []
    for _ in range(n):
        L = int(next(it))
        T = int(next(it))
        q, r = divmod(L, T)
        if r > 0 and r >= (T // 2):
            q += 1
        out.append(str(q))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.