Let's break this down carefully because the problem statement can be confusing at first.

Alice draws cards one at a time. Each card gives her a random number of points between 1 and maxPts, with equal probability (so each value has probability 1/maxPts). She keeps drawing as long as her total is strictly less than k. Once her total reaches k or more, she stops.

We need to find the probability that her final total is at most n.

Here is the key observation: Alice's final score can range from k (she was at k-1 and drew 1) up to k - 1 + maxPts (she was at k-1 and drew maxPts). Any score in the range [k, k - 1 + maxPts] is possible. We need the probability that this final score is at most n.

If k == 0, Alice never draws at all, so she stays at 0 points, and since 0 <= n, the probability is 1. If n >= k - 1 + maxPts, every possible ending score is at most n, so the probability is also 1.

This is fundamentally a probability DP problem where we build up the probability of reaching each score, then sum up the probabilities for all valid final scores.

Key Constraints:

Intuition

The most natural way to think about this: define dp[i] as the probability that Alice ends up with exactly i points at some point during the game. Alice starts at 0, so dp[0] = 1. From any score j < k, Alice draws a card valued 1 through maxPts, each with probability 1/maxPts, and moves to score j + card.

So the probability of reaching score i is:

dp[i] = sum of dp[j] / maxPts for all valid j where j = i - maxPts to j = i - 1 and j >= 0 and j < k.

The condition j < k matters because if Alice is at score j >= k, she has already stopped and won't draw more cards.

The answer is the sum of dp[i] for all i from k to n.

Algorithm

Example Walkthrough

Code

This approach works but the inner loop recomputes the same sum from scratch each time. Since the window shifts by one element per step, we can maintain a running sum instead.

Intuition

The recurrence for dp[i] involves summing a contiguous window of previous dp values:

dp[i] = (dp[i - maxPts] + dp[i - maxPts + 1] + ... + dp[i - 1]) / maxPts

But only including terms where the index is in the range [0, k-1] (since Alice stops drawing at score k or above).

When we move from computing dp[i] to dp[i+1], the window shifts by one position to the right. We add dp[i] to the window (if i < k) and remove dp[i - maxPts] from the window (if it falls out of range). This is a textbook sliding window optimization that brings the time from O(n * maxPts) down to O(n).

The crucial detail is that we only add dp[i] to the window when i < k. Once Alice reaches score k or above, she stops drawing, so those scores don't contribute to reaching higher scores.

Algorithm

Example Walkthrough

Code