273. Draw Until Twenty
In a token-drawing game you start with 0 points. Each turn you draw one integer uniformly at random from 1 to maxPts (every value equally likely, draws independent) and add it to your score. You keep drawing as long as your score is below k, and stop as soon as it reaches k or more. If k is 0 you never draw at all.
Return, as a double, the probability that your final score is at most n. Answers within 1e-9 are accepted. A direct DP that sums maxPts predecessors per score is too slow at 10^4 x 10^4, so maintain a sliding window sum to reach O(n) time and O(n) space.
Example 1
- Input:
- n = 13, k = 9, maxPts = 5
- Output:
- 1
- Explanation:
Stopping happens at a total between 9 and 13; every such total is at most 13, so the probability is 1.
Example 2
- Input:
- n = 16, k = 12, maxPts = 7
- Output:
- 0.8940651184599313
- Explanation:
Stopping totals range over 12..18, and the chance that the game ends on 16 or lower is about 0.894.
Example 3
- Input:
- n = 11, k = 10, maxPts = 6
- Output:
- 0.5344668397750174
- Explanation:
Play stops once the total reaches 10; the final total is at most 11 only if it lands on 10 or 11, which has probability about 0.53.
Constraints
0 ≤ k ≤ n ≤ 104
1 ≤ maxPts ≤ 104
Absolute error up to 1e-9 is accepted.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-9: |answer - expected| <= 1.0E-9 x max(1, |expected|).
- Tolerance
1e-9
Expected complexity
- Time
- O(n)
- Space
- O(n)