← 返回题目列表

AtCoder · abc429_d

G. AtCoder 会议

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

分数: 425 点

问题陈述

有一个池塘,周长为 M,在它的岸边矗立着一间小屋, N 人。
对于实数 x (0\leq x <M),定义点 x 作为位置 x 距小屋顺时针方向的距离。
的 树的 i- 第一个人已到达该点 A_i. 同一位置可能有多人站立。

另外,一个整数 C 不大于 给出了 N 。 对于 i=0,1,\ldots,M-1,定义 X_i 如下:

  1. 高桥从点开始 (i+0.5) 并开始顺时针移动。
  2. 高桥继续移动(顺时针),只要他遇到的总人数少于 C,并在变为时停止 C 或更多。在这里,“在某个时刻遇见一个人 y”表示高桥到达点 y.
  3. 让 X_i 是高桥在停车前遇到的人数。这里,如果高桥停下的地方有多个人,那么那里的所有人都算作他遇到的人,特别是, X_i 可能大于 C.

求总和 X_i 结束 i=0,1,\ldots,M-1,即 \displaystyle\sum_{i=0}^{M-1} X_i.

约束

  • 1\leq N\leq 5\times 10^5
  • 1\leq M\leq 10^{12}
  • 0\leq A_i\leq M-1
  • 1\leq C\leq N
  • 所有输入值均为整数。

输入

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

N M C
A_1 A_2 \ldots A_N

输出

打印总和 X_i 结束 i=0,1,\ldots,M-1 在一行上。


示例输入 1

5 3 2
1 2 1 0 1

示例输出 1

9

当 i=0,高桥从点开始 0.5 并顺时针移动。然后,会发生以下情况:

  • 在点 1,他遇到了 1圣, 3rd,和 5第人,一共三人,目前为止认识的总人数是 3。这不小于 C=2,所以高桥就停在那里。因此, X_0=3.

当 i=1,高桥从点开始 1.5 并顺时针移动。然后,会发生以下情况:

  • 在点 2,他遇到了 2第一个人。目前为止已认识的总人数为 1,所以他继续移动。
  • 在点 0,他遇到了 4第人,目前为止遇到的总人数是 2。这不小于 C=2,所以高桥就停在那里。因此, X_1=2.

当 i=2,高桥从点开始 2.5 并顺时针移动。然后,会发生以下情况:

  • 在点 0,他遇到了 4第三个人。目前为止已认识的总人数为 1,所以他继续移动。
  • 在点 1,他遇到了 1圣, 3rd,和 5第人,一共三人,目前为止认识的总人数是 4。这不小于 C=2,所以高桥就停在那里。因此, X_2=4.

因此,答案是 X_0+X_1+X_2=3+2+4=9.


示例输入 2

1 1000000000000 1
1

示例输出 2

1000000000000

无论起始位置如何,高桥在遇到唯一一个站在池塘周围的人时都会停下来。 1.
因此, X_i=1 无论 i,答案是 10^{12}.