A slow country train stops at stations 0, 1, ..., n in order, and each leg is paid separately: riding from station i to station i + 1 costs fares[i] coins (every fare is at least 1). The train only goes forward.
A traveller boards at station s with money coins and keeps paying for the next leg as long as they can afford it. Write stations_ridden(fares: list[int], travellers: list[tuple[int, int]]) -> list[int] that returns, for each traveller (s, money), how many legs they ride before they run out of money or reach the last station n.
fares = [3, 1, 4, 1, 5] # stations 0..5
stations_ridden(fares, [(0, 8), (2, 4), (1, 100), (4, 4), (5, 9)]) # [3, 1, 4, 0, 0]
# (0, 8): 3 + 1 + 4 = 8 exactly, the next leg costs 1 more -> 3 legs
# (2, 4): 4 is affordable, 4 + 1 = 5 is not -> 1 leg
# (1, 100): rides all 4 remaining legs to station 5 -> 4 legs
# (4, 4): the only leg left costs 5 -> 0 legs
# (5, 9): already at the last station -> 0 legs
Constraints: up to 10^5 fares and 10^5 travellers, 1 <= fares[i] <= 10^4, 0 <= s <= n, 0 <= money <= 10^15. Walking leg by leg for each traveller is O(n) each, too slow for the large test.
Show hint
with prefix sums P[0] = 0, P[i + 1] = P[i] + fares[i], riding from s to t costs P[t] - P[s]; since P is increasing, the farthest affordable station is the last t with P[t] <= P[s] + money, which bisect.bisect_right finds in O(log n).