/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は運送会社で働いています。今日は N 台のトラックにそれぞれ荷物を積み込む作業を担当しています。
トラック i (1 \leq i \leq N) に積み込む荷物は、1 個あたりの重さがすべて等しく P_i キログラムです。高橋君はこの荷物を 1 個ずつ積み込んでいきます。
各トラックの積載上限は共通で T キログラムです。トラック i に荷物を k 個積み込むとき、荷物の合計重量が T キログラムを超えてはいけません。すなわち、P_i \times k \leq T が成り立つ必要があります。
さらに、各トラックに積み込める荷物の個数には共通の上限 R 個が設けられています。積載上限に達していなくても、R 個を積み込んだ時点でそのトラックへの積み込みは終了します。
各トラック i について、積載上限と個数上限の両方を満たす範囲で積み込める荷物の最大個数 r_i を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq R \leq 10^9
- 1 \leq T \leq 10^{18}
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である。
入力
N R T P_1 P_2 \ldots P_N
- 1 行目には、トラックの台数を表す整数 N、各トラックに積み込める荷物の個数の上限を表す整数 R、積載上限を表す整数 T が、スペース区切りで与えられる。
- 2 行目には、各トラックに積み込む荷物 1 個あたりの重さを表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
出力
N 個の整数 r_1, r_2, \ldots, r_N をスペース区切りで 1 行で出力せよ。ここで r_i はトラック i に積み込める荷物の最大個数である。
入力例 1
3 5 20 3 5 7
出力例 1
5 4 2
入力例 2
4 10 15 1 4 8 16
出力例 2
10 3 1 0
入力例 3
10 100 1000 1 2 5 10 50 100 200 333 500 1001
出力例 3
100 100 100 100 20 10 5 3 2 0
入力例 4
20 1000000000 1000000000000000000 1 2 3 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 999999999 500000000 250000000 123456789 777777777 42 314159265 271828182
出力例 4
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
入力例 5
1 1000000000 1 1000000000
出力例 5
0
Score : 200 pts
Problem Statement
Takahashi works at a shipping company. Today, he is in charge of loading cargo onto N trucks.
The items to be loaded onto truck i (1 \leq i \leq N) all have the same weight of P_i kilograms each. Takahashi loads these items one by one.
Every truck has a common weight capacity of T kilograms. When loading k items onto truck i, the total weight of the items must not exceed T kilograms. That is, P_i \times k \leq T must hold.
Furthermore, there is a common upper limit of R items on the number of items that can be loaded onto each truck. Even if the weight capacity has not been reached, loading for that truck ends once R items have been loaded.
For each truck i, determine the maximum number of items r_i that can be loaded while satisfying both the weight capacity and the item count limit.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq R \leq 10^9
- 1 \leq T \leq 10^{18}
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N R T P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of trucks, an integer R representing the upper limit on the number of items that can be loaded onto each truck, and an integer T representing the weight capacity, separated by spaces.
- The second line contains integers P_1, P_2, \ldots, P_N representing the weight of one item to be loaded onto each truck, separated by spaces.
Output
Output N integers r_1, r_2, \ldots, r_N separated by spaces on a single line, where r_i is the maximum number of items that can be loaded onto truck i.
Sample Input 1
3 5 20 3 5 7
Sample Output 1
5 4 2
Sample Input 2
4 10 15 1 4 8 16
Sample Output 2
10 3 1 0
Sample Input 3
10 100 1000 1 2 5 10 50 100 200 333 500 1001
Sample Output 3
100 100 100 100 20 10 5 3 2 0
Sample Input 4
20 1000000000 1000000000000000000 1 2 3 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 999999999 500000000 250000000 123456789 777777777 42 314159265 271828182
Sample Output 4
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Input 5
1 1000000000 1 1000000000
Sample Output 5
0