Woburn Challenge 2016-17 Round 4 - Junior Division
Problem 2: You're Dead!
"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 policy academy, she'll need to demonstrate her skills by completing a series of N (1 ≤ N ≤ 1000) physical challenges. The i-th challenge takes place in an environment with a temperature of Ti° Celsius (−50 ≤ Ti ≤ 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 ≤ S ≤ 1000) 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° (1 ≤ L ≤ 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?
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 Ti (for i = 1..N).
Output a single line consisting of a single integer – the minimum number of days which Judy must spend training.
9 3 5 34 24 20 26 23 25 28 28 29
One optimal training schedule is as follows:
- Day 1: Challenges 1 (34°) and 9 (29°)
- Day 2: Challenges 2 (24°) and 4 (26°)
- Day 3: Challenges 3 (20°), 5 (23°), and 6 (25°)
- Day 4: Challenges 7 (28°) and 8 (28°)
Note that the temperatures of all of the challenges which Judy trains for on any single day differ by no more than 5°.
Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 09, 2017
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3