Overview

Given ribbons of length \(L_i\) to be cut into pieces of specified length \(T_i\), the problem asks to find the total number of parts obtained by following this rule: in addition to the basic number of pieces cut out, “if the leftover scrap length is at least half of \(T_i\), add one more part.”

Analysis

• The ribbon length \(L_i\) and part length \(T_i\) can be as large as \(10^{18}\). Therefore, a naive simulation that repeatedly subtracts \(T_i\) from \(L_i\) in a loop would result in an enormous number of iterations and cause TLE (Time Limit Exceeded).
• Instead, we take the approach of computing the answer directly using arithmetic operations.
• The basic number of parts that can be cut is obtained as the quotient \(\lfloor L_i / T_i \rfloor\).
• The length of the leftover scrap after cutting is obtained as the remainder \(L_i \bmod T_i\).
• Then, following the rule in the problem statement, we check whether this remainder is greater than \(0\) and at least \(\lfloor T_i / 2 \rfloor\). If the condition is satisfied, we add \(+1\) to the part count.

Concrete examples: - When \(L_i = 10, T_i = 3\): - The quotient is \(10 \div 3 = 3\), the remainder is \(10 \bmod 3 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 3 / 2 \rfloor = 1\) - The remainder \(1\) is at least \(1\), so the condition is satisfied, and the number of parts is \(3 + 1 = 4\). - When \(L_i = 10, T_i = 4\): - The quotient is \(10 \div 4 = 2\), the remainder is \(10 \bmod 4 = 2\) - \(\lfloor T_i / 2 \rfloor = \lfloor 4 / 2 \rfloor = 2\) - The remainder \(2\) is at least \(2\), so the condition is satisfied, and the number of parts is \(2 + 1 = 3\).

Algorithm

For each ribbon, compute as follows: 1. Calculate the quotient of \(L_i\) divided by \(T_i\), and use this as the basic number of parts. 2. Calculate the remainder \(R_i\) of \(L_i\) divided by \(T_i\), and use this as the scrap length. 3. Use an if statement to check whether \(R_i > 0\) and \(R_i \geq \lfloor T_i / 2 \rfloor\). 4. If the condition is satisfied, add \(1\) to the basic number of parts. 5. Append the computed number of parts to the output list.

Repeat this process for all \(N\) ribbons, and output the results together at the end.

Complexity

• Time complexity: \(O(N)\)
  • The division and remainder computation for a single ribbon completes in \(O(1)\). Repeating this \(N\) times gives an overall time complexity of \(O(N)\).
• Space complexity: \(O(N)\)
  • We use lists to read all input data at once and to store the output results, requiring \(O(N)\) memory.

Implementation Notes

• In Python, integer quotient (floor division) can be easily computed with the // operator, and the remainder with the % operator.

• Since the number of ribbons \(N\) can be as large as \(2 \times 10^5\), calling the standard input() tens of thousands of times can cause slowdowns due to I/O processing overhead. Therefore, we use sys.stdin.read().split() to read all input at once, and accumulate the output in an array before printing it all at once with '\n'.join(). This significantly reduces the execution time.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    out = []
    
    it = iter(input_data[1:])
    for L_str, T_str in zip(it, it):
        L = int(L_str)
        T = int(T_str)
        
        ans = L // T
        R = L % T
        
        if R > 0 and R >= T // 2:
            ans += 1
            
        out.append(str(ans))
        
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.