COCI '17 Contest 4 #1 Rasvjeta

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

It is Advent season. There are M street lights in a street N metres long (the meters of the street are denoted with numbers from 1 to N). Each of the lights lights up the meter of the street it's located in and K meters to the left and to the right of that location. In other words, if the light is located at meter X, it lights up all metres of the street from X - K to X + K, inclusively. Of course, it is possible for a meter of the street to be lit up by multiple street lights. All lights have distinct locations.

The problem is that there is a possibility that the lights don't light up all N metres of the street. It is your task to determine the minimal amount of additional lights needed to be put up (at position from 1 to N) so that the entire street is lit up.

Input Specification

The first line of input contains the number N\ (1 \le N \le 1000).
The second line of input contains the number M\ (1 \le M \le N).
The third line contains the number K\ (0 \le K \le N).
Each of the following M lines contains a number. The numbers are sorted in ascending order and represent the positions of each of the M street lights.
The positions will be distinct and from the interval [1, N].

Output Specification

You must output the required number from the task.

Sample Input 1

5
2
2
1
5

Sample Output 1

0

Clarification of the first test case:
It's not necessary to add lights to the street, since all N meters are already lit up.

Sample Input 2

26
3
3
3
19
26

Sample Output 2

2

Sample Input 3

13
2
10
1
2

Sample Output 3

1

Clarification of the third test case:
It is necessary to add one lamp, for example at location 13.


Comments

There are no comments at the moment.