CF949D Curfew

某信息学院的老师让学生们按时就寝。 这栋房子有 $n$ 个房间，每个房间本应有恰好 $b$ 个学生睡觉。然而，在宵禁时刻，许多学生并不在他们被分配的房间里。房间排成一排，编号为 $1$ 到 $n$。最初，第 $i$ 个房间里有 $a_i$ 个学生。所有学生都在这栋房子里，因此 $a_1 + a_2 + \dots + a_n = n b$。此外，这栋房子里住着两位老师。 宵禁执行过程如下：一位老师从第 $1$ 号房间开始，向第 $n$ 号房间移动；另一位老师从第 $n$ 号房间开始，向第 $1$ 号房间移动。每位老师在处理当前房间后，继续前往下一个房间。两位老师会同时进入房间并移动，如果 $n$ 是奇数，则只有第一位老师会处理中间的房间。当所有房间都被处理完后，过程结束。 当老师处理一个房间时，她会数一下房间里的学生人数，然后关灯并锁门。如果房间里的学生人数不等于 $b$，老师会把这个房间的编号记在笔记本上（然后关灯并锁门）。老师们很着急（要准备第二天的教学计划），所以她们只关心房间里有多少学生，而不在乎具体是谁。 在老师们进入房间时，学生们可以在尚未被锁且未被处理的房间之间奔跑。每个学生最多可以跨越 $d$ 个房间，也就是说，她可以移动到编号相差不超过 $d$ 的房间。此外，每个学生在奔跑之后（或不奔跑时）可以选择藏在她所在房间的床下，这样老师在检查时就不会数到她。每个房间可以有任意数量的学生同时藏起来。 形式化地，过程如下： - 宵禁宣布时，第 $i$ 个房间有 $a_i$ 个学生。 - 每个学生可以跑到距离她原始房间不超过 $d$ 的另一个房间，或者留在原地。之后，每个学生可以选择藏在床下。 - 老师进入第 $1$ 号房间和第 $n$ 号房间，数清楚房间里的学生人数并锁门（之后没人能进出该房间）。 - 编号为 $2$ 到 $n-1$ 的房间里的每个学生可以跑到距离她当前房间不超过 $d$ 的另一个房间，或者留在原地。每个学生可以选择藏在床下。 - 老师分别从第 $1$ 号房间移动到第 $2$ 号房间，从第 $n$ 号房间移动到第 $n-1$ 号房间。 - 如此反复，直到所有房间都被处理完。 设 $x_1$ 表示第一位老师在她检查的房间中，数到的未藏匿学生人数不等于 $b$ 的房间数，$x_2$ 表示第二位老师的同样统计。学生们知道校长只会听取一位老师的投诉，因此他们希望最小化 $x_i$ 中的最大值。请帮他们求出在最优策略下，这个最大值的最小可能值。

第一行包含三个整数 $n$、$d$ 和 $b$（$2 \leq n \leq 100000$，$1 \leq d \leq n-1$，$1 \leq b \leq 10000$），分别表示房间数、学生最大奔跑距离、每个房间应有的学生数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示宵禁宣布时第 $i$ 个房间的学生数。 保证 $a_1 + a_2 + \dots + a_n = n b$。

输出一个整数，表示 $x_1$ 和 $x_2$ 的最小可能最大值。

在第一个样例中，前 $3$ 个房间由第一位老师处理，最后两个房间由第二位老师处理。一种最优策略是：首先 $3$ 个学生从第 $5$ 个房间跑到第 $4$ 个房间，下一轮其中 $2$ 个跑到第 $3$ 个房间，其中 $1$ 个藏在床下。这样，第一位老师会记下第 $2$ 个房间，第二位老师不会记下任何房间。 在第二个样例中，一种最优策略是：首先第 $1$ 个房间的所有学生都藏起来，第 $2$ 个房间的所有学生跑到第 $3$ 个房间。下一轮有 $1$ 个学生从第 $3$ 个房间跑到第 $4$ 个房间，$5$ 个学生藏起来。这样，第一位老师会记下第 $1$ 和第 $2$ 个房间，第二位老师会记下第 $5$ 和第 $6$ 个房间。 由 ChatGPT 4.1 翻译