Fewest charging stops for the van
An electric delivery van starts fully charged with a range of R kilometres and must drive D kilometres along a straight road. Charging stations sit at known distances from the start, and every stop restores a full charge. Print the fewest stops needed to reach the destination. If it cannot be reached, print unreachable.
Input
The first line holds three integers: the range R (1 to 1000000), the distance D (1 to 1000000000) and the number of stations M (0 to 1000). The second line holds M strictly increasing integers, the station positions, each between 1 and D - 1. When M is 0 the second line is empty.
Output
One line: the minimum number of stops, or unreachable.
Example 1
Input
100 350 4 90 150 230 300
Output
4
With 100 km of range the van reaches only the station at 90. From there 150 is the farthest reachable, then 230, then 300, and from 300 the destination at 350 is within range: four stops.
Example 2
Input
50 120 1 40
Output
unreachable
After charging at 40 the van can reach 90, and there is no station between 40 and 90, so the remaining 80 km cannot be covered.
Example 3
Input
500 300 0
Output
0
The destination is within the initial range, so no stop is needed even though there are no stations.
Constraints
- 1 <= R <= 1000000
- 1 <= D <= 1000000000
- 0 <= M <= 1000
- Station positions are strictly increasing and lie strictly between 0 and D
Hints
Hint 1 of 3
Track how far the van can currently get: $reach, which starts at R.
Hint 2 of 3
While $reach is less than D, look at the stations at or before $reach and pick the farthest one; that is the greedy choice. If there is none, the trip is impossible.
Hint 3 of 3
After a stop at position p the new reach is p + R. Because the stations are sorted, one index that only moves forward is enough to find the farthest reachable station.
Solution
Show a reference solution and explanation
<?php
[$range, $distance, $m] = array_map('intval', explode(' ', trim(fgets(STDIN))));
$line = fgets(STDIN);
$stations = ($m > 0 && $line !== false && trim($line) !== '')
? array_map('intval', explode(' ', trim($line)))
: [];
$stops = 0;
$reach = $range;
$i = 0;
while ($reach < $distance) {
$farthest = -1;
while ($i < $m && $stations[$i] <= $reach) {
$farthest = $stations[$i];
$i++;
}
if ($farthest === -1) {
echo "unreachable\n";
exit;
}
$stops++;
$reach = $farthest + $range;
}
echo $stops, "\n";
Why it works
The greedy rule is: when a stop is unavoidable, stop as far along the road as the current charge allows. It is safe because stopping earlier can never get the van further than stopping at the farthest reachable station, so it never reduces the options for the rest of the trip. Stations are given in increasing order, so a single index that only ever moves forward scans each station once, and the whole plan costs O(M). Two edge cases decide correctness: reaching the destination with the initial charge (zero stops, possibly with an empty second line, which is why the solution checks fgets for false and for an empty line), and a gap between stations longer than the range, which shows up as no station within reach and prints unreachable.
Lesson for this exercise: Conditions and Loops in PHP