Exam in BerSU (easy version)

题意翻译

# 注意事项 $\text{CF1185C2}$是本题的数据加强版，所以，做出本题不意味着你一定能过$\text{CF1185C2}$。 # 题目描述 白朗州大学的又一个学年到来了，很多学生都在做测试。 我们的主人公，小$\text{P}$，要去测试$n(1\leqslant n\leqslant 100)$位学生。学生们将按照$1$到$n$的顺序依次测试。考试规则如下。 - 第$i$个考生随机抽取一张标签，上面有题目。 - 如果这个考生认为这个题目太难，TA没有做这个题目就滚回家去了，那么TA这次考试不及格。 - 如果这个考生发现题目很容易，并且刚好用了$t_i$分钟完成了这道题目。那么过后，TA将带着得到的考试分数回家。 学生们按照固定的次序，依次没有中断地测试。在任何时候，小$\text{P}$从一个学生当中得到答案。 所有学生的考试时间的总和是$M(1\leqslant M\leqslant 100)$，其中保证$\max t[i]\leqslant M$，所以，成绩不好的学生更有可能花光时间以通过考试。 对于每个学生$i$，你的任务是当TA通过考试时，计算出前面最少的不及格的学生的人数。 例如以下的样例一，前5个学生做完题目所需要的时间刚好等于M，所以，他们都不需要不及格的人，所以最少的不及格人数是0。而为了让第6和第7个学生通过测试，前面分别必须让第3,4和第2,5,6个学生不及格。 # 输入输出格式 ## 输入 输入包含2行。第一行，给出两个数$n$和$M$（含义和范围已在题面给出），第二行给出$n$个数，其中第$i$个数表示第$i$个学生做完题目所需要的时间$t_i$。 输入保证每个$t_i$都小于$M$。 ## 输出 输出仅一行，$n$个数，第$i$个数表示为了如果第$i$个人完成任务，前面最小的不及格的人数。 ## 样例 ### Sample1 #### 输入 7 15 1 2 3 4 5 6 7 #### 输出 0 0 0 0 0 2 3 ### Sample2 #### 输入 5 100 80 40 40 40 60 #### 输出 0 1 1 2 3

题目描述

The only difference between easy and hard versions is constraints. A session has begun at Beland State University. Many students are taking exams. Polygraph Poligrafovich is going to examine a group of $ n $ students. Students will take the exam one-by-one in order from $ 1 $ -th to $ n $ -th. Rules of the exam are following: - The $ i $ -th student randomly chooses a ticket. - if this ticket is too hard to the student, he doesn't answer and goes home immediately (this process is so fast that it's considered no time elapses). This student fails the exam. - if the student finds the ticket easy, he spends exactly $ t_i $ minutes to pass the exam. After it, he immediately gets a mark and goes home. Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student. The duration of the whole exam for all students is $ M $ minutes ( $ \max t_i \le M $ ), so students at the end of the list have a greater possibility to run out of time to pass the exam. For each student $ i $ , you should count the minimum possible number of students who need to fail the exam so the $ i $ -th student has enough time to pass the exam. For each student $ i $ , find the answer independently. That is, if when finding the answer for the student $ i_1 $ some student $ j $ should leave, then while finding the answer for $ i_2 $ ( $ i_2>i_1 $ ) the student $ j $ student does not have to go home.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ M $ ( $ 1 \le n \le 100 $ , $ 1 \le M \le 100 $ ) — the number of students and the total duration of the exam in minutes, respectively. The second line of the input contains $ n $ integers $ t_i $ ( $ 1 \le t_i \le 100 $ ) — time in minutes that $ i $ -th student spends to answer to a ticket. It's guaranteed that all values of $ t_i $ are not greater than $ M $ .

输出格式

Print $ n $ numbers: the $ i $ -th number must be equal to the minimum number of students who have to leave the exam in order to $ i $ -th student has enough time to pass the exam.

输入输出样例

输入样例 #1

7 15
1 2 3 4 5 6 7

输出样例 #1

0 0 0 0 0 2 3 

输入样例 #2

5 100
80 40 40 40 60

输出样例 #2

0 1 1 2 3 

说明

The explanation for the example 1. Please note that the sum of the first five exam times does not exceed $ M=15 $ (the sum is $ 1+2+3+4+5=15 $ ). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are $ 0 $ . In order for the $ 6 $ -th student to pass the exam, it is necessary that at least $ 2 $ students must fail it before (for example, the $ 3 $ -rd and $ 4 $ -th, then the $ 6 $ -th will finish its exam in $ 1+2+5+6=14 $ minutes, which does not exceed $ M $ ). In order for the $ 7 $ -th student to pass the exam, it is necessary that at least $ 3 $ students must fail it before (for example, the $ 2 $ -nd, $ 5 $ -th and $ 6 $ -th, then the $ 7 $ -th will finish its exam in $ 1+3+4+7=15 $ minutes, which does not exceed $ M $ ).