Curfew

题意翻译

### 题目描述 一些信息学学校的宿管要赶人上床睡觉了。 宿舍有 $n$ 个寝室，在每个寝室里头都应有 $b$ 个学生。但是，在静校的时候，有的学生是不在他们应该在的宿舍的。寝室排成一行并且从 $1$ 到 $n$ 编号。起初，在第 $i$ 个寝室有 $a_i$ 个学生。所有的学生都在宿舍里的某个地方，因此 $a_1+a_2+\cdots+a_n=nb$ 。并且宿舍里有 $2$ 个宿管。 静校过程是这样的：一个宿管从 $1$ 号寝室走到 $n$ 号寝室，另一个宿管从 $n$ 号寝室走到 $1$ 号寝室。在查完一个宿舍后，宿管就会去查下一个宿舍。宿管同时进入/离开宿舍。如果 $n$ 是奇数，则第一个宿管，则只有第一个宿管查中间那个宿舍。当所有宿舍都被查过，则静校过程完毕。 当一个宿管进入一个宿舍的时候，她数一下这个宿舍里有多少个学生，然后关灯锁门。并且，如果这个宿舍的人数不是 $b$ ，宿管会把这个宿舍的编号写到小本本上（然后也关灯锁门）。宿管很忙，所以她们并不关系是谁在这个宿舍，只关心学生的人数。 形式化的，静校过程是这样的： - 宣布静校开始，此刻寝室 $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,\ldots,a_n$ （$0 \leq a_i \leq 10^9$ ），第 $i$ 个是在静校前在第 $i$ 个寝室的人数。 保证 $a_1+a_2+\cdots+a_n=nb$ 。 ### 输入格式 输出一个整数，$x_i$ 的最大值的可能的最小的数。 Translated by @poorpool

题目描述

Instructors of Some Informatics School make students go to bed. The house contains $ n $ rooms, in each room exactly $ b $ students were supposed to sleep. However, at the time of curfew it happened that many students are not located in their assigned rooms. The rooms are arranged in a row and numbered from $ 1 $ to $ n $ . Initially, in $ i $ -th room there are $ a_{i} $ students. All students are currently somewhere in the house, therefore $ a_{1}+a_{2}+...+a_{n}=nb $ . Also $ 2 $ instructors live in this house. The process of curfew enforcement is the following. One instructor starts near room $ 1 $ and moves toward room $ n $ , while the second instructor starts near room $ n $ and moves toward room $ 1 $ . After processing current room, each instructor moves on to the next one. Both instructors enter rooms and move simultaneously, if $ n $ is odd, then only the first instructor processes the middle room. When all rooms are processed, the process ends. When an instructor processes a room, she counts the number of students in the room, then turns off the light, and locks the room. Also, if the number of students inside the processed room is not equal to $ b $ , the instructor writes down the number of this room into her notebook (and turns off the light, and locks the room). Instructors are in a hurry (to prepare the study plan for the next day), so they don't care about who is in the room, but only about the number of students. While instructors are inside the rooms, students can run between rooms that are not locked and not being processed. A student can run by at most $ d $ rooms, that is she can move to a room with number that differs my at most $ d $ . Also, after (or instead of) running each student can hide under a bed in a room she is in. In this case the instructor will not count her during the processing. In each room any number of students can hide simultaneously. Formally, here is what's happening: - A curfew is announced, at this point in room $ i $ there are $ a_{i} $ students. - Each student can run to another room but not further than $ d $ rooms away from her initial room, or stay in place. After that each student can optionally hide under a bed. - Instructors enter room $ 1 $ and room $ n $ , they count students there and lock the room (after it no one can enter or leave this room). - Each student from rooms with numbers from $ 2 $ to $ n-1 $ can run to another room but not further than $ d $ rooms away from her current room, or stay in place. Each student can optionally hide under a bed. - Instructors move from room $ 1 $ to room $ 2 $ and from room $ n $ to room $ n-1 $ . - This process continues until all rooms are processed. Let $ x_{1} $ denote the number of rooms in which the first instructor counted the number of non-hidden students different from $ b $ , and $ x_{2} $ be the same number for the second instructor. Students know that the principal will only listen to one complaint, therefore they want to minimize the maximum of numbers $ x_{i} $ . Help them find this value if they use the optimal strategy.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ d $ and $ b $ ( $ 2<=n<=100000 $ , $ 1<=d<=n-1 $ , $ 1<=b<=10000 $ ), number of rooms in the house, running distance of a student, official number of students in a room. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=10^{9} $ ), $ i $ -th of which stands for the number of students in the $ i $ -th room before curfew announcement. It is guaranteed that $ a_{1}+a_{2}+...+a_{n}=nb $ .

输出格式

Output one integer, the minimal possible value of the maximum of $ x_{i} $ .

输入输出样例

输入样例 #1

5 1 1
1 0 0 0 4

输出样例 #1

1

输入样例 #2

6 1 2
3 8 0 1 0 0

输出样例 #2

2

说明

In the first sample the first three rooms are processed by the first instructor, and the last two are processed by the second instructor. One of the optimal strategies is the following: firstly three students run from room $ 5 $ to room $ 4 $ , on the next stage two of them run to room $ 3 $ , and one of those two hides under a bed. This way, the first instructor writes down room $ 2 $ , and the second writes down nothing. In the second sample one of the optimal strategies is the following: firstly all students in room $ 1 $ hide, all students from room $ 2 $ run to room $ 3 $ . On the next stage one student runs from room $ 3 $ to room $ 4 $ , and $ 5 $ students hide. This way, the first instructor writes down rooms $ 1 $ and $ 2 $ , the second instructor writes down rooms $ 5 $ and $ 6 $ .

题意翻译

### 题目描述 一些信息学学校的宿管要赶人上床睡觉了。 宿舍有 $n$ 个寝室，在每个寝室里头都应有 $b$ 个学生。但是，在静校的时候，有的学生是不在他们应该在的宿舍的。寝室排成一行并且从 $1$ 到 $n$ 编号。起初，在第 $i$ 个寝室有 $a_i$ 个学生。所有的学生都在宿舍里的某个地方，因此 $a_1+a_2+\cdots+a_n=nb$ 。并且宿舍里有 $2$ 个宿管。 静校过程是这样的：一个宿管从 $1$ 号寝室走到 $n$ 号寝室，另一个宿管从 $n$ 号寝室走到 $1$ 号寝室。在查完一个宿舍后，宿管就会去查下一个宿舍。宿管同时进入/离开宿舍。如果 $n$ 是奇数，则第一个宿管，则只有第一个宿管查中间那个宿舍。当所有宿舍都被查过，则静校过程完毕。 当一个宿管进入一个宿舍的时候，她数一下这个宿舍里有多少个学生，然后关灯锁门。并且，如果这个宿舍的人数不是 $b$ ，宿管会把这个宿舍的编号写到小本本上（然后也关灯锁门）。宿管很忙，所以她们并不关系是谁在这个宿舍，只关心学生的人数。 形式化的，静校过程是这样的： - 宣布静校开始，此刻寝室 $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,\ldots,a_n$ （$0 \leq a_i \leq 10^9$ ），第 $i$ 个是在静校前在第 $i$ 个寝室的人数。 保证 $a_1+a_2+\cdots+a_n=nb$ 。 ### 输入格式 输出一个整数，$x_i$ 的最大值的可能的最小的数。 Translated by @poorpool