Night Bus Loop
HardOnline Assessment
Follow a night bus around a ring road, counting how many times it reaches the depot.
The route has n = len(skips) stops numbered 0 to n - 1 around a ring: after stop n - 1 comes stop 0 again, and the depot is stop 0. The bus starts at stop start. Its driver reads the number skips[i] posted at the stop i he is at and takes that many stops, which can be more than a full circle. The bus makes hops hops in total, numbered 1, 2, 3, ...:
- a normal hop moves the bus forward
skips[i]stops; - every
k-th hop (hopsk,2k,3k, ...) is a reverse hop: the bus moves backwardskips[i]stops instead.
Posted numbers never change. A hop that ends at stop 0 is a depot landing. Only where a hop ends counts: the starting position is not a landing even if start is 0, and a stop the bus merely passes is not a landing. If a hop moves the bus a whole number of circles, it ends where it began (and that counts as a landing if that stop is 0).
Input: skips, start, k and hops.
Output: [stop, landings]: the stop the bus is at after all hops, and the number of depot landings.
Example 1
- Input:
- [[2,1,3,1,2],0,3,6]
- Output:
- [0,2]
- Explanation
- Five stops, skips 2, 1, 3, 1, 2; the bus starts at stop 0 and every 3rd hop is a reverse hop. Hop 1: 0 forward 2 to stop 2. Hop 2: 2 forward 3 to stop 0 (first depot landing). Hop 3 is a reverse hop: from stop 0 back 2 to stop 3. Hop 4: 3 forward 1 to stop 4. Hop 5: 4 forward 2 to stop 1. Hop 6 is a reverse hop: from stop 1 back 1 to stop 0 (second landing). The bus is at stop 0 and has landed on the depot twice.
Example 2
- Input:
- [[3,1,1],0,2,7]
- Output:
- [0,7]
- Explanation
- Three stops with skips 3, 1, 1 and k = 2; the bus starts at the depot. A skip of 3 on a ring of 3 stops is one whole circle, so every hop from stop 0 ends back at stop 0, forward or backward. Each of the 7 hops is therefore a depot landing, even though the starting position itself is not counted. Final answer: stop 0, 7 landings.
Example 3
- Input:
- [[4,7,5,9,2,8],2,4,1000000000000]
- Output:
- [2,250000000000]
- Explanation
- Six stops with skips 4, 7, 5, 9, 2, 8, starting at stop 2, k = 4, and 1012 hops: hopping one at a time is far too slow. The situation repeats as soon as the same (stop, position within the group of k hops) pair is seen again, so the route is a short lead-in followed by a cycle. Count the depot landings in one pass of the cycle, multiply by the number of whole cycles that fit, and replay only the few leftover hops. The bus ends at stop 2 after 250000000000 depot landings.
Constraints
- 1 ≤ skips.length ≤ 2000; 1 ≤ skips[i] ≤ 109
- 0 ≤ start < skips.length
- 1 ≤ k ≤ 60
- 0 ≤ hops ≤ 1015