Woburn Challenge 2016-17 Round 2 - Junior Division

Problem 2: EHC

"Please state the nature of the culinary emergency!" exclaims the Enterprise's EHC (Emergency Holographic Chef), having just been activated. It seems that Lieutenant Commander Le Ferge is extremely hungry, and will need to be brought a hot meal, stat!

The EHC is currently in the mess hall, and will need to make his way to the bridge to save Le Ferge. The bridge is at the end of a hallway, which is M (1 ≤ M ≤ 10⁹) metres long. There's just one complication – being a hologram, the EHC must remain within a distance of R (1 ≤ R ≤ 10⁹) metres (inclusive) of a holographic emitter at all times.

Fortunately, there's a holographic emitter installed right at the entrance to the mess hall, and there are N (0 ≤ N ≤ 200,000) other emitters located at various points along the hallway. The i-th of these emitters is E_i (1 ≤ E_i < M) metres away from the mess hall (and thus, M − E_i metres away from the bridge). No two emitters are in the same location.

The existing set of N + 1 holographic emitters may not provide enough unbroken coverage for the EHC to be able to successfully walk from the mess hall to the bridge. If that's the case, some more emitters may need to be installed along the hallway, at any chosen locations.

Le Ferge is very, very hungry, and only the EHC is qualified enough to feed him! Given that time is of the essence, what's the minimum number of additional holographic emitters which must be installed in order for every point in the hallway to be at most R metres away from at least one emitter?

In test cases worth 8/20 of the points, N ≤ 2000 and M ≤ 2000.
In test cases worth another 8/20 of the points, N ≤ 2000.

Input Format

The first line of input consists of three space-separated integers N, M, and R.
N lines follow, with the i-th of these lines consisting of a single integer E_i (for i = 1..N).

Output Format

Output a single integer – the minimum number of additional emitters required.

Sample Input

2 100 15
85
61

Sample Output

2

Explanation

One possibility is to place two holographic emitters 30 metres and 40 metres away from the mess hall. If only the first of these emitters is added, then the EHC won't be able to traverse the section of the hallway between 45 and 46 metres from the mess hall (exclusive).

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Dec 11, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)