시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 (추가 시간 없음) | 512 MB | 53 | 8 | 8 | 18.605% |
There are M contestants in a certain contest. The ith contestant garnered Pi points, for i = 1,2,...,M.
The organizers have N balloons which shall be awarded to the contestants in the following manner:
The problem is to find the number of balloons that are awarded to each contestant.
Here’s an example. Consider the case with M = 5 contestants having the following points:
Suppose there are N = 10 balloons. Then the allocation is (approximately) given as follows:
j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 | j = 7 | ... | |
---|---|---|---|---|---|---|---|---|
#1 | 274771.00 | 137385.50 | 91590.33 | 68692.75 | 54954.20 | 45795.17 | 39253.00 | ... |
#2 | 344854.00 | 172427.00 | 114951.33 | 86213.50 | 68970.80 | 57475.67 | 49264.86 | ... |
#3 | 773780.00 | 386890.00 | 257926.67 | 193445.00 | 154756.00 | 128963.33 | 110540.00 | ... |
#4 | 627629.00 | 313814.50 | 209209.67 | 156907.25 | 125525.80 | 104604.83 | 89661.29 | ... |
#5 | 386890.00 | 193445.00 | 128963.33 | 96722.50 | 77378.00 | 64481.67 | 55270.00 | ... |
The ranks of each of these ratios near 10 are given as follows:
j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 | j = 7 | ... | |
---|---|---|---|---|---|---|---|---|
#1 | 7 | 15 | * | * | * | * | * | ... |
#2 | 5 | 12 | 19 | * | * | * | * | ... |
#3 | 1 | 3 | 8 | 10 | 14 | 16 | * | ... |
#4 | 2 | 6 | 9 | 13 | 18 | * | * | ... |
#5 | 3 | 10 | 16 | * | * | * | * | ... |
Therefore, the number of balloons given to each of the 5 contestants is 1, 1, 4, 3 and 2, respectively.
Notice also that 11 balloons are awarded in total. This is because two ratios tied at rank 10.
The first line of input contains T, the number of test cases.
The first line of each test case contains two integers, M and N, separated by a space. The second line contains M space-separated integers P1, P2, ..., PM.
Constraints
For each test case, output M integers separated by single spaces, the i th of which denotes the number of balloons the i th contestant receives.
2 5 10 274771 344854 773780 627629 348561 5 10 274771 344854 773780 627629 386890
1 1 4 3 1 1 1 4 3 2