You start with 0 points. While your total is below k, you draw a card worth a uniformly random integer in 1..max_pts (each draw independent) and add it. As soon as your total reaches k or more, you stop.
Write new21_game(n: int, k: int, max_pts: int) -> float returning the probability that your final total is at most n. Answers within 1e-6 of the exact value are accepted.
Constraints: 0 <= k <= n <= 10**4, 1 <= max_pts <= 10**4.
new21_game(5, 1, 10) # 0.5: one draw, and 1..5 out of 1..10 are fine
new21_game(3, 2, 3) # 0.8888...: 8/9
new21_game(0, 0, 7) # 1.0: you never draw
Aim for O(n + max_pts) time: an O(n * max_pts) solution is about 10^8 steps at the limits.
Hint: Each p[x] sums a window of up to max_pts earlier values. Keep that window's sum as you go instead of recomputing it.
Show hint
Let p[x] be the probability of ever standing on total x, with p[0] = 1. Each p[x] comes from the totals you could have drawn from, but only those still below k, since from k on you've stopped. The answer is the sum of p[x] for k <= x <= n.