问题 5090 --天佑榨橙汁

5090: 天佑榨橙汁

时间限制: 1 Sec  内存限制: 128 MB
提交: 732  解决: 269
[提交][状态][命题人:]

题目描述

天佑想要制作新鲜的橙汁,他有n个大小为1 ,  2 , ...,  n的橙子,天佑将按照给出的固定顺序依次将它们放入榨汁机中,首先是大小为1的橙子,然后是大小为2的橙子,依此类推。要放入榨汁机,橙子的大小必须不超过b,所以如果天佑看到一个大小超过b的橙子,他会扔掉它并继续放入下一个。

对于成功放入榨汁机的橙子,在榨取时会产生废弃物,榨汁机有一个专门的地方来收集这些废弃物。如果天佑榨取的橙子的总大小超过d(严格大于),废弃物就会溢出来。这时,天佑会清空废物区,并继续榨取橙汁(即使之后没有橙子了,也会清空废物区)。请问当他榨完所有橙子后,他需要清空废弃区多少次?

输入

输入的第一行包含三个整数nbd ( 1 ≤  n  ≤ 100 000 , 1 ≤  b  ≤  d  ≤ 1 000 000) ,分别表示橙子的数量、可放入榨汁机的橙子的最大尺寸和废物区的大小d

第二行包含n 个整数1 ,  2 , ...,  n ( 1 ≤  i  ≤ 1 000 000 ) ,将橙子的大小按天佑放入榨汁机的顺序列出。

输出

一个整数,表示天佑需要清空废弃区的次数。

样例输入
Copy
2 7 10
5 6
样例输出
Copy
1

提示

样例2输入

1 5 10
7

样例2输出

0

样例3输入

3 10 10
5 7 7

样例3输出

1

样例4输入

1 1 1
1

样例4输出

0

针对样例1,两个橙子被放入榨汁机后,需要清理一次废弃区。

针对样例2,橙子不能被放入榨汁机中,所以不用清理废弃区。

来源

[提交][状态]