Overview

Given \(N\) trucks, the problem asks to find the maximum number of items that can be loaded onto each truck while satisfying two constraints: a weight limit (total at most \(T\) kilograms) and a quantity limit (at most \(R\) items).

Analysis

For each truck \(i\), letting \(k\) be the number of items to load, the following two conditions must be satisfied:

1. Weight limit: Since each item weighs \(P_i\), the total weight is \(P_i \times k\). This must be at most \(T\), so \(P_i \times k \leq T\) must hold.
2. Quantity limit: There is an upper bound on the number of items itself, so \(k \leq R\) must hold.

First, consider the maximum value of \(k\) from condition 1 (weight limit). Solving the inequality \(P_i \times k \leq T\) for \(k\) gives \(k \leq \frac{T}{P_i}\). Since \(k\) is an integer, the maximum value of \(k\) from this condition is the quotient of \(T\) divided by \(P_i\) (rounded down). We denote this as \(k_{weight} = \lfloor T / P_i \rfloor\).

Next, consider condition 2 (quantity limit) \(k \leq R\). The desired maximum number \(r_i\) is the largest integer satisfying both constraints simultaneously, so: $\(r_i = \min(R, \lfloor T / P_i \rfloor)\)$

Since \(N\) can be as large as \(2 \times 10^5\), we need to compute each truck’s result efficiently. Since the formula above can be computed in \(O(1)\), the overall complexity is \(O(N)\), which is well within the time limit.

Algorithm

1. Read \(N, R, T\) and each \(P_i\) from the input.
2. For each \(i = 1, \dots, N\), perform the following computation:
   • Compute the maximum number of items from the weight limit: \(k_{weight} = T \text{ // } P_i\) (integer floor division).
   • Set \(r_i\) to the smaller of \(k_{weight}\) and \(R\).
3. Output the computed \(r_i\) values in order, separated by spaces.

Complexity

• Time complexity: \(O(N)\)
  • Since the computation for each truck takes constant time, the total processing time is proportional to the number of trucks \(N\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input values \(P_i\) and the output results.

Implementation Notes

• Handling large numbers: Since \(T\) can be as large as \(10^{18}\), depending on the programming language, you may need to use a 64-bit integer type (such as long long). In Python, arbitrary-precision integers are supported by default, so you can compute without worrying about overflow.

• Fast I/O: Since \(N\) is large, in Python it is effective to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly, and to output all at once using sys.stdout.write(), which helps reduce execution time.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します。
    # Nが最大2*10^5と大きいため、一括読み込みが効率的です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 最初の3つの要素は N (トラック台数), R (積み込み回数上限), T (積載制限) です。
    n = int(input_data[0])
    r_limit = int(input_data[1])
    t_limit = int(input_data[2])
    
    # 各トラックの結果を格納するためのリストを事前に確保します。
    results = [None] * n
    
    # 各トラック i について、過積載にならずに積み込める最大回数 r_i を計算します。
    # k 回目の積み込みが完了した時点での重さは P_i * k です。
    # 過積載にならない条件は P_i * k <= T なので、k <= T / P_i となります。
    # したがって、最大回数は floor(T / P_i) と R の小さい方になります。
    for i in range(n):
        # input_data[i + 3] が各トラックの P_i に対応します。
        p_i = int(input_data[i + 3])
        
        # Pythonの // 演算子は整数の切り捨て除算（floor division）を行います。
        max_possible_loads = t_limit // p_i
        
        # 積み込み回数上限 R を超えないように制限します。
        if max_possible_loads > r_limit:
            r_i = r_limit
        else:
            r_i = max_possible_loads
        
        # 出力用に文字列に変換してリストに格納します。
        results[i] = str(r_i)
    
    # 全ての結果をスペース区切りで1行に出力します。
    sys.stdout.write(" ".join(results) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-thinking.