You need to get from floor 0 to floor n. You ride the elevator for the first k floors (you choose k, 0 <= k <= n) and climb the stairs for the other n - k.
- Elevator: each floor takes
t1time, and resting in the elevator builds upe1energy per floor. So after the ride you havek * e1energy and have usedk * t1time. - Stairs: each stair floor costs
e2energy. If your energy isEwhen you start a stair floor, that floor takesc / Etime (real division: rested legs are faster). You may only start a stair floor whileE > 0.
Choosing k too small leaves you exhausted (or unable to climb at all); choosing it too large wastes time in the elevator. Write
def fastest_climb(n: int, e1: int, t1: int, e2: int, c: int) -> float
returning the smallest total time over all valid k. (k = n never touches the stairs, so there is always an answer.) Results are compared with a relative tolerance of 1e-9.
fastest_climb(3, 2, 5, 1, 6)
# k=0: 0 energy, can't climb k=1: 5 + 6/2 + 6/1 = 14
# k=2: 10 + 6/4 = 11.5 k=3: 15
# -> 11.5
fastest_climb(4, 3, 10, 1, 3) # 15.5 (k=1: 10 + 3/3 + 3/2 + 3/1)
Constraints: 1 <= n <= 100,000; 1 <= e1, t1, e2 <= 10,000; 1 <= c <= 10**9.
Computing the total for one k takes O(n), so trying every k is O(n^2), too slow for n = 100,000. You need about log n evaluations.
Show hint
Look at how validity and T(k) (the total time for a given k) behave as k grows: validity is monotone, and among valid k the step T(k + 1) - T(k) only increases, because each extra elevator floor costs a fixed t1 while its savings on the stairs shrink. Both properties let you find the best k with O(log n) evaluations of T.