Description
Suppose that N
apartments are placed in a row. In some apartments among these, 4g base station is installed at the rooftop. As demand for 5g increases due to the advancement of technology, you want to replace 4g base station with 5g base station. But, since the coverage of 5g base station is smaller than 4g base station, some apartments cannot receive signal after replacing 4g base station with 5g base station.
For example, assume that 11 apartments are places in a row, and 4g base station is installed at the rooftop of [4, 11]-th apartment. If these 4g base stations are replaced with 5g base station with coverage of length 1, signal is not delivered to all apartments. (When the coverage is length W
, signal is delivered within the range of W
from both side of apartment where base station is installed.)
- At the beginning, apartments at the position of 1, 2, 6, 7, 8, and 9 cannot receive the signal.
- If the 5g base station is installed at the apartments of position 1, 7, and 9, signal is delivered to all apartments.
- In the case of installing 5g base station at more than 3 apartments, signal is delivered to all apartments.
At this point, you want to deliver the signal to all apartments by installing the minimum number of base stations. In the above example, installing at least 3 base stations is required to deliver signal to all apartments.
Given the number of apartments N
, an 1-dimensional array stations
containing the position of apartments where 4g base station is installed, and the coverage of base station W
as parameters, write a function solution
to return the minimum number of base stations to be installed additionally to deliver the signal for all apartments.
Constraints
N
: natural number less than 200,000,000.- Length of
stations
: natural number less than 10,000. stations
is sorted in ascending order, and its elements are natural number less thanN
.W
: natural number less than 10,000.
Examples
N | stations | W | answer |
---|---|---|---|
11 | [4, 11] | 1 | 3 |
16 | [9] | 2 | 3 |
Example #1
This is the same with the example in the problem statement.
Example #2
- At the initial stage, signal is not delivered to the apartments of position 1~6 and 12~16.
- When installing the base station at the apartments of position 3, 6, and 14, signal is delivered to all apartments.