How Do I Code This? On Which Algorithm Of Dynamic Programing Is It Based On?

See more:

Java

code-generation

Your company is building cell-phone towers along a straight railway line at points p[0], p[1], …, p[n-1]. The company must construct temporary houses for workers, and wants to ensure two conditions: (i) from every point p[i], the distance to the nearest house should be at most k; and (ii) the number of temporary houses should be as small as possible.
Input: The input will consist of several lines, each containing one number as follows:
The first line will have the number n (0 < n < 100000)
The second line will have the number k (0 < k < n)
The next n lines will contain the values
p[0]
p[1]
:
p[n1] (one value per line)
Note: The numbers p[0], p[1], …, p[n-1] are NOT sorted, and for each value of i, 0 <p[i]>< 10n.
Output: Write a program that prints the (integer) locations at which to construct houses, one integer per line, in INCREASING order. You must also ensure that your program satisfies conditions (i) and (ii) above. Your program should print NOTHING ELSE.
Some sample inputs and outputs are given below. Note that the outputs of your program need not match these outputs exactly – what matters is that conditions (i) and (ii) are satisfied and that the numbers are printed in INCREASING order.
Sample input 1:
5
3
15
8
9
1
12
Sample output 1:
1
10
15