Problem D
Bombardment
You are designing an old-school game you call Bombardment where the goal is to destroy a number of points by bombarding them. You do not yet know the theme of your game, just that the core mechanics should involve a bombardment.
The points to be destroyed are located on the real number
line, that is each point is simply an
You decide to playtest a basic version of this game before you go through the effort of designing a theme, adding nice graphics, etc. Interestingly, most testers seemed to employ a greedy strategy: each bombardment is chosen to destroy the maximum number of points in that single bombardment. Sometimes, this causes players to use more bombardments than the minimum possible number of bombardments. You want to design a program that will simulate this strategy, this will help you design interesting levels.
That is, your job is to write a program that will simulate
the following process. While there are still points remaining,
choose a value
Input
The first line of input contains two integers
Output
The first line of output contains a single integer
Sample Input 1 | Sample Output 1 |
---|---|
7 1 1 2 3 3 4 4 5 |
3 3 0 4 |
Sample Input 2 | Sample Output 2 |
---|---|
6 1 5 -2 5 0 1 2 |
3 1 4 -3 |
Sample Input 3 | Sample Output 3 |
---|---|
6 2 5 -2 5 0 1 2 |
2 0 3 |
Sample Input 4 | Sample Output 4 |
---|---|
6 3 5 -2 5 0 1 2 |
2 2 -5 |