概要

各リボンについて \(L_i\) を \(T_i\) で割った「商」と「余り」を使い、余りが条件を満たすときだけパーツ数を \(+1\) する問題です。

考察

重要なのは「実際に \(T_i\) ミリずつ切る作業をシミュレーションする必要はない」という点です。
\(i\) 本目のリボンでは

• まず通常のパーツは \(\lfloor L_i / T_i \rfloor\) 個できる
• 余り \(R_i = L_i \bmod T_i\) が残る
• その余りが 残っていて（\(R_i>0\)）、かつ 半分以上（\(R_i \ge \lfloor T_i/2 \rfloor\)）なら、余りも 1 個のパーツとして数える

と書かれています。

ここで素朴に「\(T_i\) ずつ切っていく」シミュレーションをすると、例えば \(L_i\) が \(10^{18}\) など非常に大きいときに切る回数が最大 \(10^{18}\) 回になり、当然時間内に終わりません（TLE）。
しかし必要なのは「何回切れるか」と「余りはいくつか」だけなので、整数の割り算（商と余り）一発で求められます。

具体例： - \(L=13,\,T=5\) のとき \(13=5\times2+3\) なので \(q=2, r=3\)
\(\lfloor T/2 \rfloor =2\)、\(r=3 \ge 2\) かつ \(r>0\) より、答えは \(2+1=3\) - \(L=11,\,T=5\) のとき \(q=2, r=1\)
\(r(=1) < 2\) なので答えは \(2\)

また \(L<T\) でも同様に、\(q=0, r=L\) となり、余り条件を満たせば 1 個、満たさなければ 0 個になります。

アルゴリズム

各リボン \((L, T)\) について次を行います。

1. \(q, r = \mathrm{divmod}(L, T)\) として
   \(q=\lfloor L/T \rfloor\)（作れる通常パーツ数）、\(r=L\bmod T\)（余り）を得る
2. もし \(r>0\) かつ \(r \ge \lfloor T/2 \rfloor\) なら \(q \leftarrow q+1\)
3. \(q\) を出力する

この通りに実装すれば、そのまま \(P_i\) の定義を計算できます。

計算量

• 時間計算量: \(O(N)\)（各リボンにつき定数時間の計算）
• 空間計算量: \(O(1)\)（出力用を除く）

実装のポイント

• Python では divmod(L, T) を使うと商と余りを同時に得られて簡潔です。

• 条件は問題文通りに r > 0 and r >= (T // 2) とします（\(r=0\) のときは追加しない点に注意）。

• \(N\) が最大 \(2\times10^5\) なので、入力は sys.stdin.buffer.read() を使うと高速です。

  ソースコード

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

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