← 返回题目列表

Codeforces · 949/D

D. 宵禁

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

某信息学院的老师让学生上床睡觉。

房子有 n 个房间,每个房间正好有 b 个学生应该睡觉。然而,在宵禁期间,许多学生并不在指定的房间里。房间排列成一排,编号为 1 到 n。最初,第 i 个房间里有 a 个学生。所有学生目前都在房子的某个地方,因此 a1 + a2 + ... + an = nb。这座房子里还住着 2 名教练。

宵禁执行过程如下。一名讲师从房间 1 附近开始,向房间 n 移动,而第二名讲师从房间 n 附近开始,向房间 1 移动。处理完当前房间后,每位讲师都会移至下一个房间。两个教练同时进入房间并移动,如果n是奇数,则只有第一个教练处理中间的房间。当所有房间都处理完毕后,该过程结束。

当讲师处理一个房间时,她会计算房间内的学生人数,然后关灯并锁上房间。另外,如果处理后的房间内的学生人数不等于b,则教师将该房间的编号记入她的笔记本中(并关掉灯,并锁上房间)。导师们很着急(准备第二天的学习计划),所以他们不关心房间里有谁,只关心学生的数量。

当教师在房间内时,学生可以在未上锁且未处理的房间之间奔跑。一个学生最多可以跑过 d 个房间,即她最多可以移动到与我的编号不同 d 的房间。此外,在运行之后(或代替运行),每个学生都可以躲在她所在房间的床下。在这种情况下,教师在处理过程中不会计算她的数量。每个房间中可以同时隐藏任意数量的学生。

正式来说,发生的事情是这样的:

- 宣布宵禁,此时i房间里有ai学生。
- 每个学生都可以跑到另一个房间,但距离她最初的房间不超过 d 个房间,或者留在原地。之后,每个学生都可以选择躲在床下。
- 教师进入房间 1 和房间 n,他们统计那里的学生并锁定房间(之后任何人都不能进入或离开这个房间)。
- 编号为 2 到 n - 1 的房间的每个学生都可以跑到另一个房间,但距离当前房间不超过 d 个房间,或者留在原地。每个学生都可以选择躲在床下。
- 讲师从房间 1 移动到房间 2,并从房间 n 移动到房间 n - 1。
- 此过程将继续,直到处理完所有房间。

设 x1 表示第一个讲师计算出与 b 不同的非隐藏学生数量的房间数,x2 表示第二个讲师的相同数字。学生们知道校长只会听取一个投诉,因此他们希望尽量减少最大数量 xi。如果他们使用最佳策略,请帮助他们找到这个价值。

输入

第一行包含三个整数 n、d 和 b(2 ≤ n ≤ 100 000、1 ≤ d ≤ n - 1、1 ≤ b ≤ 10 000)、房屋中的房间数、学生的跑步距离、房间中的正式学生人数。

第二行包含n个整数a1, a2, ..., an (0 ≤ ai ≤ 109),其中i代表宵禁宣布前第i个教室的学生人数。

保证a1 + a2 + ... + an = nb。

输出

输出一个整数,xi 的最大值的最小可能值。

示例

输入 #1

5 1 1
1 0 0 0 4

输出 #1

1

输入 #2

6 1 2
3 8 0 1 0 0

输出 #2

2

注意

在第一个示例中,前三个房间由第一个讲师处理,后两个房间由第二个讲师处理。最佳策略之一如下:首先三名学生从 5 号房间跑到 4 号房间,下一阶段其中两名学生跑到 3 号房间,其中两名学生之一躲在床下。这样,第一个讲师会写下房间 2,而第二个讲师则什么也不写。

在第二个示例中,最佳策略如下:首先,房间 1 中的所有学生都躲起来,房间 2 中的所有学生都跑到房间 3。在下一阶段,一个学生从房间 3 跑到房间 4,然后 5 个学生隐藏。这样,第一个讲师写下房间 1 和 2,第二个讲师写下房间 5 和 6。