传统题 1000ms 256MiB

T2

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

又到了白色相簿的季节,𝑤𝑏𝑦独自漫步于清水塘畔的街道,这条街道长为𝑁米,有𝑀个路灯被 安装在这条路上,每一个路灯可以照亮前后各𝐾米的街道。比如说,如果有一个路灯位于街道𝑋米 处,那么从𝑋 − 𝐾米到𝑋 + 𝐾米处都可以被这个路灯照亮。 𝑊𝑏𝑦希望整条街道都可以被照亮,因此他需要在原有的基础上添加路灯,然而他又不希望光 芒过于闪耀,他希望可以添加尽量少的灯。 你的任务就是帮助𝑤𝑏𝑦求出他最少需要添加几盏路灯才能照亮整条街道。(数据保证路灯只 在整数米处且没有两个路灯会在同一位置)。

Format

Input

第一行输入一个正整数𝑁(1 ≤ 𝑁 ≤ 1000),表示街道的长度。 第二行输入一个正整数𝑀(1 ≤ 𝑀 ≤ 𝑁),表示初始路灯的数目。 第三行输入一个正整数𝐾(0 ≤ 𝐾 ≤ 𝑁),表示一盏灯可以照亮的范围。 接下来的𝑀行,每行一个正整数𝑃𝑖(1 ≤ 𝑃𝑖 ≤ 𝑁),表示第𝑖盏路灯的位置。 .

Output

输出𝑤𝑏𝑦需要添加的最少的路灯数。

Samples

5
2
2
1
5
0
26
3
3
3
19
26
2
13
2
10
1
2
1

样例解释

对于样例一,我们无需再添加路灯,这条街道已经被全部点亮了。 对于样例三,至少需要添加一盏路灯,一个可行的方案是在第13米处放置一个路灯。

夏季清凉赛

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-10 18:30
结束于
2023-7-10 20:15
持续时间
1.8 小时
主持人
参赛人数
124