DWITE
November 2012
Problem 5
Car Hoppers

'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 2 numbers separated by a space: 1 <= N, M <= 1000, which are the Number of cars in the lot and the Maximum distance the guards can see in the fog. The following N lines will contain a single integer 1 <= H <= 1000, the Height of each car, in order.

The output file OUT5.txt will contain 5 lines of output. Each line 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 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.