DWITE Online Computer Programming Contest

Car Hoppers

November 2012
Problem 5

“Car-hopping” is a common pastime of programmers that involves them hopping atop of cars parked in a lot (it gives them something to do while waiting for their code to compile). After having received multiple complaints, the parking lot company decided to hire guards to stand on top of cars to prevent programmers from car-hopping. However, there are certain factors the guards should take into account:

Given the predicament they are in, the company decides to hire a programmer (one of the founders of “car-hopping” nonetheless!) to help them determine the minimum number of guards needed.

The input file DATA5.txt will contain 5 test cases. The first line of each test case contains two numbers separated by a space: 1 ≤ N, M ≤ 1000, which are the (N)umber of cars in the lot and the (M)aximum distance the guards can see in the fog. The following N lines will each contain a single integer 1 ≤ H ≤ 1000, the (H)eight of the car, in order.

The output file OUT5.txt will contain 5 lines. Each is a single integer representing the minimum number of guards necessary to monitor the parking lot for the corresponding case.

Sample Input (first 2 shown):
5 2
2
2
2
2
2
5 2
2
1
3
4
1
Sample Output (first 2 shown):
1
2

Notes: In the first case, a single guard can be placed on the middle car, and the range of 2 in each direction will cover the entire lot. In the second case, such a strategy will not work, as a guard in the middle (height 3) is blocked by the following car (height 4) from monitoring the last car of the lot.