← 返回题目列表

Codeforces · 677/B

B. Vanya 和食品加工机

中文机器翻译题面 查看原题

Vanya 在立式食品加工机中捣碎土豆。在每个时刻,处理机中马铃薯的高度不超过 h,并且处理机每秒粉碎 k 厘米的马铃薯。如果剩余的马铃薯少于 k 厘米,则在第二个处理器中会粉碎所有剩余的马铃薯。

Vanya 有 n 块土豆,第 i 块的高度等于 ai。他将它们从 1 号物品开始,一直到 n 号物品,一件一件地放入食品加工机中。正式来说,每一秒都会发生以下情况:

1. 如果至少还剩下一块土豆,Vanya 会将它们一块一块地放入处理器中,直到没有足够的空间容纳下一块。
2. 处理器粉碎 k 厘米的土豆(或里面的所有东西)。

提供食品加工机的参数和连续每个土豆的大小信息,计算需要多长时间才能将所有土豆打碎。

输入

输入的第一行包含整数 n、h 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109)——分别是土豆片的数量、食品加工机的高度和每秒粉碎的土豆量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ h) — 棋子的高度。

输出

打印一个整数——按照问题陈述中描述的过程粉碎所有土豆所需的秒数。

示例

输入 #1

5 6 3
5 4 3 2 1

输出 #1

5

输入 #2

5 6 3
5 5 5 5 5

输出 #2

10

输入 #3

5 6 3
1 2 1 1 1

输出 #3

2

注意

考虑第一个样本。

1. 首先 Vanya 将高度为 5 的马铃薯块放入加工机中。在第二个结束时,内部只剩下高度 2。
2. 现在,Vanya 放入了高度为 4 的土豆块。第二次结束时,剩余高度为 3 的土豆。
3. Vanya 将高度为 3 的棋子放入内部,在这一秒结束时再次只剩下 3 厘米。
4. Vanya 最后将高度为 2 和 1 的棋子放入其中。第二步结束时,处理机中马铃薯的高度等于 3。
5. 在第二个处理器中,最终粉碎了所有剩余的马铃薯,并且该过程完成。

在第二个样本中,Vanya 将高度为 5 的碎片放入其中并等待 2 秒,直至其完全粉碎。然后他对另外 4 件作品重复相同的过程。总时间等于2·5 = 10 秒。

在第三个示例中,Vanya 只是将所有土豆放入处理器中并等待 2 秒。