ICPC PACNW 2016 C - Cameras

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 256M

Problem type
Allowed languages
C, C#, C++, Java, Python

Your street has nn houses, conveniently numbered from 11 to nn. Out of these nn houses, kk of them have security installed. Mindful of gaps in coverage, the Neighborhood Watch would like to ensure that every set of rr consecutive houses has at least two different houses with cameras. What is the minimum number of additional cameras necessary to achieve this?

Input

The first line of input contains three integers, nn (2 \le n \le 100\,000)(2 \le n \le 100\,000), kk (0 \le k \le n)(0 \le k \le n), and rr (2 \le r \le n)(2 \le r \le n).

The next kk lines of input contain the distinct locations of the existing cameras.

Output

Print, on a single line, a single integer indicating the minimum number of cameras that need to be added.

Sample Input

15 5 4
2
5
7
10
13

Sample Output

3
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.