DMOPC '14 Contest 6 P4 - Bus Jam - DMOJ: Modern Online Judge

DMOPC '14 Contest 6 P4 - Bus Jam

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

On a certain route, buses are initially evenly spaced; however, due to the inconsistent traffic flow, one bus can get slightly delayed. As that bus becomes increasingly crowded due to the greater number of passengers at each stop, it gets delayed even further while the bus behind it catches up. This leads to buses travelling in packs where the first bus is full and the last one is almost empty.

As the buses (and especially the passengers) get jammed, one solution is to make the almost empty buses wait for a certain number of minutes so that there can be a reasonable gap.

Given a list of buses and the length of time that it is away from the terminus, find the minimum number of $M$ ~M~-minute breaks required so that all buses will have headways (the length of time between buses) of at most $H$ ~H~ minutes.

Each bus has the choice of taking any number of $M$ ~M~-minute breaks, even if it means being overtaken by another bus or waiting until the next day.

Input Specification

The first line of input will contain three space-separated integers, $N$ ~N~ $(1 \le N \le 1\,000)$ ~(1 \le N \le 1\,000)~, which represents the number of buses, $M$ ~M~ $(1 \le M \le 100)$ ~(1 \le M \le 100)~, the duration of one break, and $H$ ~H~ $(1 \le H \le 100)$ ~(1 \le H \le 100)~, the desired headway (length of time between buses).

The next $N$ ~N~ lines contain $T$ ~T~ $(0 \le T \le 10\,000)$ ~(0 \le T \le 10\,000)~, the length of time in minutes in which the bus is expected to arrive at the terminus. The times will be sorted in ascending order.

Output Specification

Output the minimum number of $M$ ~M~-minute breaks that will occur.
It is guaranteed that it will be possible to achieve a headway of at most $H$ ~H~ minutes.

Sample Input

Sample Output

Explanation for Sample Output

The first bus can take two breaks while the second and third buses can take one break each.
All headways are now $10$ ~10~ minutes or less, as required.

bus pack

Comments

4
d commented on Dec. 26, 2015, 11:38 p.m. ← edited →
What would be the output for this case?

3 9 5 6 10 20

1
sz_8 commented on Sept. 23, 2022, 1:59 a.m. ← edited →
Output from my solution that AC'd:

2

0

pyrexshorts commented on April 7, 2015, 9:08 p.m. ← edited →

Between the first bus and the second bus, there is 12 minutes of headway, but there needs to be 2 breaks? Shouldn't it be 1 break so that the headway is 10 minutes?

Edit: nvm, got it.

1

Sentient commented on April 7, 2015, 9:16 p.m.

If the first bus takes a break, its value changes to 3, but then the other buses also have to take breaks...try solving for the sample on paper...