Overview

When cutting parts of a specified length from each ribbon, if the leftover scrap meets certain conditions, it can be counted as one additional part. Based on this rule, determine the number of parts obtainable from each ribbon.

Analysis

For each ribbon, the following processing needs to be performed: - First, divide the ribbon length \(L_i\) by the specified part length \(T_i\) to obtain the quotient \(\lfloor L_i / T_i \rfloor\), which represents the parts that can definitely be used. - Next, compute the remainder \(R_i = L_i \bmod T_i\). - If this remainder is greater than 0 and \(R_i \geq \lfloor T_i / 2 \rfloor\), then the scrap is also counted as one part.

For example, when \(L_i = 7\), \(T_i = 3\): - Quotient: \(\lfloor 7 / 3 \rfloor = 2\) → 2 parts - Remainder: \(7 \bmod 3 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 3 / 2 \rfloor = 1\) - \(R_i = 1 \geq 1\), so the scrap counts as 1 part → total of 3

On the other hand, when \(L_i = 5\), \(T_i = 4\): - Quotient: \(\lfloor 5 / 4 \rfloor = 1\) → 1 part - Remainder: \(5 \bmod 4 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 4 / 2 \rfloor = 2\) - \(R_i = 1 < 2\), so the scrap cannot be used → total of 1

Issues with a Naive Approach

If input is read line by line from standard input, since \(N\) can be up to \(2 \times 10^5\), the input reading alone may take too long and result in TLE. Additionally, since \(L_i, T_i\) can be up to \(10^{18}\), division and modulo operations need to be handled efficiently.

Solution

Use Python’s sys.stdin.read to read all input at once for faster processing. Furthermore, by using the divmod function, the quotient and remainder can be obtained simultaneously, enabling efficient and simple processing.

Algorithm

1. Read all input at once and store it in a list.
2. For each ribbon, perform the following:
   • Use divmod(L, T) to obtain the quotient \(q\) and remainder \(r\).
   • Compute half of \(T\) as half_T = T // 2.
   • If the condition \(r > 0\) and \(r \geq \text{half\_T}\) is satisfied, the answer is \(q + 1\).
   • Otherwise, the answer is \(q\).
3. Store results as strings in a list, then join them with newlines and output all at once.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Use sys.stdin.read to efficiently handle large amounts of input.

• Use divmod to obtain the quotient and remainder simultaneously.

• Store results as strings and output them all at once to reduce output processing overhead.

• In the condition check, accurately implement “\(r > 0\) and \(r \geq \lfloor T/2 \rfloor\)”.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    idx = 1
    results = []
    for _ in range(N):
        L = int(data[idx])
        T = int(data[idx+1])
        idx += 2
        q, r = divmod(L, T)
        half_T = T // 2
        if r > 0 and r >= half_T:
            results.append(str(q + 1))
        else:
            results.append(str(q))
    print('\n'.join(results))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.