F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Find the answer

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4927    Accepted Submission(s): 1554


Problem Description
Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements $W_k$ (1 <= k < i), and change them to zero to make $\sum_{j=1}^i$$W_j$<=m. So what's the minimum number of chosen elements to meet the requirements above?.
 

Input
The first line contains an integer Q --- the number of test cases.
For each test case:
The first line contains two integers n and m --- n represents the number of elemens in sequence W and m is as described above.
The second line contains n integers, which means the sequence W.

1 <= Q <= 15
1 <= n <= 2*$10^5$
1 <= m <= $10^9$
For each i, 1 <= $W_i$ <= m
 

Output
For each test case, you should output n integers in one line: i-th integer means the minimum number of chosen elements $W_k$ (1 <= k < i), and change them to zero to make $\sum_{j=1}^i$$W_j$<=m.
 

Sample Input
2 7 15 1 2 3 4 5 6 7 5 100 80 40 40 40 60
 

Sample Output
0 0 0 0 0 2 3 0 1 1 2 3
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 14:07:52, Gzip enabled