시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 99 | 54 | 48 | 60.759% |
Your street has n houses, conveniently numbered from 1 to n. Out of these n houses, k of them have security cameras installed. Mindful of gaps in coverage, the Neighborhood Watch would like to ensure that every set of r consecutive houses has at least two different houses with cameras. What is the minimum number of additional cameras necessary to achieve this?
The first line of input contains three integers, n (2 ≤ n ≤ 100,000), k (0 ≤ k ≤ n), and r (2 ≤ r ≤ n).
The next k lines of input contain the distinct locations of the existing cameras.
Print, on a single line, a single integer indicating the minimum number of cameras that need to be added.
15 5 4 2 5 7 10 13
3