← 返回题目列表

AtCoder · abc353_b

D. AtCoder游乐园

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

分数: 200 点

问题陈述

AtCoder游乐园有一个景点,可以容纳 K 人。现在,有 N 团体在该景点排队。

的 树的 i前数第 组 (1\leq i\leq N) 包括 A_i 人。对于所有人 i (1\leq i\leq N),它认为 A_i \leq K.

高桥作为该景点的工作人员,将按照以下流程引导排队的团体。

最初没有人引导到景点,有 K 空座位。

  1. 如果队列中没有团体,则开始景点并结束引导。
  2. 将景点中的空座位数与队列前面的团体人数进行比较,并执行以下操作之一:
    • 如果空座位数少于前面的团体人数,则开始景点。那么空座位数就变成了 再次 K 。
    • 否则,引导队列前面的整个团队前往景点。前面的一组被从队列中移除,空座位的数量随着该组中的人数而减少。
  3. 返回步骤 1。

此处,指导开始后不会再有其他团体排队。在这些条件下,可以证明该过程将以有限数量的步骤结束。

确定在整个指导过程中景点将启动多少次。

约束

  • 1\leq N\leq 100
  • 1\leq K\leq 100
  • 1\leq A_i\leq K\ (1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

7 6
2 5 1 4 1 2 3

示例输出 1

4

最初,七个小组的排列如下:

高桥指导的部分内容如下图所示:

  • 最初,前面的小组有 2 人,还有 6 空座位。于是,他带领前队前往景点,离开 4 空座位。
  • 接下来,前面的小组有 5 人,这比 4 座位空了,所以景点开始了。
  • 景点启动后,有 6 座位又空了,所以前面的队伍被引导到景点,离开 1 空座位。
  • 接下来,前面的小组有 1 人,所以他们被引导到景点,离开 0 空座位。

在引导完成之前,他总共启动了四次景点。 因此,打印 4.


示例输入 2

7 10
1 10 1 10 1 10 1

示例输出 2

7

示例输入 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

示例输出 3

8