Description
Alice draws cards 1 to maxPts until sum >= k. She wins if sum <= n. Given n, k, maxPts, return the probability she has at most n points.
Examples
n = 10, k = 1, maxPts = 101.0Stop at 1, can't exceed 10.
n = 21, k = 17, maxPts = 100.73278Alice draws until she has at least 17 points. From any score in [17,21], she stops and wins. From scores below 17, she draws 1-10 more points. The probability calculation involves multiple paths where she can exceed 21, making this a complex case demonstrating the dynamic programming nature of the problem.
n = 5, k = 2, maxPts = 30.83333Alice stops when she reaches 2+ points. Starting from 0, she draws 1-3 points. If she gets 1, she draws again and can get 2,3,4 (all ≤5, so wins). If she initially gets 2 or 3, she stops immediately and wins. Only losing scenario is getting 1 then drawing 3 more for total 4, then potentially exceeding 5 on forced continuation.
Constraints
- •
0 ≤ k ≤ n ≤ 10⁴