837. New 21 Game

Medium

Alice plays a game inspired by the card game 21.

• She starts with 0 points.
• While her score is less than $k$, she draws numbers.
• Each draw adds a random integer from $[1, \; \text{maxPts}]$, with equal probability.
• The game stops once her score reaches k or more.

You need to return the probability that Alice finishes with n or fewer points.

An answer is correct if it is within $10^{-5}$ of the true value.

---

Examples

Example 1
Input:
$n = 10, \; k = 1, \; \text{maxPts} = 10$

Output:
$1.00000$

Explanation: Alice only draws once, so she will always stop with $\leq 10$ points.

---

Example 2
Input:
$n = 6, \; k = 1, \; \text{maxPts} = 10$

Output:
$0.60000$

Explanation: Alice only draws once.
The possible outcomes are $1,2,3,4,5,6,7,8,9,10$.
In 6 out of 10 cases, she has $\leq 6$ points.

---

Example 3
Input:
$n = 21, \; k = 17, \; \text{maxPts} = 10$

Output:
$0.73278$

---

Constraints

• $0 \leq k \leq n \leq 10^4$
• $1 \leq \text{maxPts} \leq 10^4$