Overview

For each truck, the problem asks to find the maximum number of items that can be loaded while satisfying both the weight limit \(T\) and the quantity limit \(R\).

Analysis

When loading \(k\) items onto truck \(i\), the following two conditions must be satisfied simultaneously:

1. Weight constraint: \(P_i \times k \leq T\) (total weight does not exceed the loading capacity)
2. Quantity constraint: \(k \leq R\) (number of items does not exceed the upper limit)

From condition 1, the maximum number of items that can be loaded considering only weight is \(k \leq \lfloor T / P_i \rfloor\). Here, \(\lfloor \cdot \rfloor\) denotes the floor function (integer division).

For example, when \(T = 100\) and \(P_i = 30\), we get \(\lfloor 100 / 30 \rfloor = 3\), so at most 3 items can be loaded by weight (\(30 \times 3 = 90 \leq 100\), \(30 \times 4 = 120 > 100\)).

The final answer is the minimum of the maximum number from the weight constraint \(\lfloor T / P_i \rfloor\) and the quantity limit \(R\):

\[r_i = \min\left(\left\lfloor \frac{T}{P_i} \right\rfloor, R\right)\]

This calculation can be done independently for each truck in \(O(1)\), so simply looping over all trucks is sufficiently fast. No special algorithm is needed.

Algorithm

1. Read \(N\), \(R\), \(T\) from input.
2. For each truck \(i\) (\(1 \leq i \leq N\)):
   • Read the weight of one item \(P_i\).
   • Compute the maximum number of items by weight constraint: \(\lfloor T / P_i \rfloor\).
   • Compute \(r_i = \min(\lfloor T / P_i \rfloor, R)\).
3. Output \(r_1, r_2, \ldots, r_N\) separated by spaces.

Concrete example: For \(N=3\), \(R=5\), \(T=100\), \(P = [30, 10, 50]\):

Complexity

• Time complexity: \(O(N)\) (\(O(1)\) computation per truck, repeated \(N\) times)
• Space complexity: \(O(N)\) (array to store the results)

Implementation Notes

• Since \(T\) can be as large as \(10^{18}\), in languages like C++ you need to use the long long type. In Python, there is no integer overflow, so this is not a concern.

• T // P is Python’s integer division, which automatically performs floor division.

• Since the input can be large, reading all input at once with sys.stdin.buffer.read() provides a speedup.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    R = int(input_data[1])
    T = int(input_data[2])
    
    results = []
    for i in range(N):
        P = int(input_data[3 + i])
        # Maximum k such that P * k <= T, i.e., k <= T // P
        max_k = T // P
        if max_k >= R:
            results.append(R)
        else:
            results.append(max_k)
    
    sys.stdout.write(' '.join(map(str, results)) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.