概要

各トラックについて「重さ制限 \(T\)」と「個数制限 \(R\)」の両方を満たす範囲で、積み込める荷物の最大個数 \(r_i\) を求めます。

考察

トラック \(i\) に荷物を \(k\) 個積むときの条件は次の 2 つです。

• 重さ制限: \(P_i \times k \leq T\)
• 個数制限: \(k \leq R\)

重さ制限から、積める個数の上限は $\( k \leq \left\lfloor \frac{T}{P_i} \right\rfloor \)$ となります（整数なので切り捨て）。

したがって、両方の制限を同時に満たす最大の個数は $\( r_i = \min\left(R,\ \left\lfloor \frac{T}{P_i} \right\rfloor\right) \)$ です。

素朴に「1個ずつ積んでいって制限に達するまで数える」と、最悪で各トラックにつき \(R\) 回（最大 \(10^9\) 回）操作が必要になり、\(N\) も最大 \(2 \times 10^5\) なので到底間に合いません（TLE）。
しかし上の式を使えば、各トラックは割り算 1 回で答えが出ます。

例: - \(T=10,\ R=7,\ P_i=3\) のとき、重さ制限だけなら \(\left\lfloor 10/3 \right\rfloor=3\) 個まで。個数制限 \(7\) より小さいので \(r_i=\min(7,3)=3\)。

アルゴリズム

1. 入力として \(N, R, T\) と配列 \(P\) を読む。
2. 各トラック \(i\) について \(x = T // P_i\)（整数除算）を計算する。
3. \(r_i = \min(R, x)\) を答えとして出力する。

計算量

• 時間計算量: \(O(N)\)（各トラックにつき定数時間）
• 空間計算量: \(O(N)\)（入力配列と出力配列）

実装のポイント

• \(T\) は最大 \(10^{18}\) なので、言語によっては 64bit 整数が必要です（Python は多倍長整数なので安全）。

• \(N\) が大きいので、Python では sys.stdin.buffer.read() のような高速入力を使うと安定します。

• 求めるのは切り捨ての商なので、T // p（整数除算）を使います。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, R, T = data[0], data[1], data[2]
    P = data[3:3+N]
    res = [str(min(R, T // p)) for p in P]
    sys.stdout.write(" ".join(res))

if __name__ == "__main__":
    main()

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