WC '16 Contest 4 J2 - You're Dead!

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Woburn Challenge 2016-17 Round 4 - Junior Division

"Scorching sandstorm! You're dead, bunny bumpkin."
"One-thousand-foot fall! You're dead, carrot face!"
"Frigid ice wall! You're dead, farm girl!"
"Enormous criminal! You're dead!"

Judy Hopps is determined to earn her place onto Zootopia's Police Department as the city's first rabbit cop, but it won't be easy. In order to graduate from the police academy, she'll need to demonstrate her skills by completing a series of N (1 \le N \le 1\,000) physical challenges. The i-th challenge takes place in an environment with a temperature of T_i^\circ Celsius (-50 \le T_i \le 50). Judy has decided to dedicate one training session to each challenge in advance to ensure that she'll then ace it in her graduation exam.

On every day leading up to the exam, Judy will have time for at most S (1 \le S \le 1\,000) training sessions. In each session, she can choose one challenge to train for. However, there's a limit to how quickly her body is able to adapt to wildly varying temperatures. As such, the temperatures of all of the challenges which Judy trains for on any single day must differ from one another by no more than L^\circ (1 \le L \le 100). In other words, for each day, the difference between the maximum and the minimum temperatures of all of the challenges chosen on that day must be no greater than L.

Judy will only take her graduation exam once she's spent one training session on each of the N challenges, but she'd love for that to be the case as soon as possible – she needs to get out there and make the world a better place! Given that she optimally chooses which challenges to dedicate each day's training sessions to, what's the minimum number of days which she must spend training before she's sufficiently prepared?

Input Specification

The first line of input consists of three space-separated integers N, S, and L.
N lines follow, the i-th of which consists of a single integer T_i (for i = 1 \dots N).

Output Specification

Output a single line consisting of a single integer – the minimum number of days which Judy must spend training.

Sample Input

9 3 5
34
24
20
26
23
25
28
28
29

Sample Output

4

Sample Explanation

One optimal training schedule is as follows:

  • Day 1: Challenges 1 (34^\circ) and 9 (29^\circ)
  • Day 2: Challenges 2 (24^\circ) and 4 (26^\circ)
  • Day 3: Challenges 3 (20^\circ), 5 (23^\circ), and 6 (25^\circ)
  • Day 4: Challenges 7 (28^\circ) and 8 (28^\circ)

Note that the temperatures of all of the challenges which Judy trains for on any single day differ by no more than 5^\circ.


Comments

There are no comments at the moment.