0575MediumMathDynamic ProgrammingSliding WindowProbability and Statistics

Token Counter Stop Rule

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A fairground machine keeps a running tally of tokens, starting at 0.

The machine works like this. While the tally is strictly below k, it dispenses one more handful and adds it to the tally. A handful holds a whole number of tokens drawn from 1 to maxPts, and every one of those maxPts amounts is equally likely, independently of anything dispensed before. As soon as the tally is k or more the machine stops for good. If the tally already meets k before anything is dispensed, the machine never dispenses at all.

Return the probability that the tally the machine stops on is at most n, rounded to 6 decimal places.

Examples

Example 1

Input: n = 5, k = 1, maxPts = 10
Output: 0.5

One handful is dispensed and then the tally is at least 1, so the machine stops. Five of the ten equally likely amounts, namely 1 through 5, leave a tally of at most 5.

Example 2

Input: n = 4, k = 5, maxPts = 1
Output: 0.0

Every handful holds exactly one token, so the machine stops the moment the tally reaches 5, and 5 is above 4.

Example 3

Input: n = 12, k = 3, maxPts = 6
Output: 1.0

The machine can stop on any tally from 3 to 8, and 12 is above all of them, so the answer is 1.

Constraints

0 <= k <= n <= 10^4
1 <= maxPts <= 10^4
The answer is the exact probability rounded to 6 decimal places.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def new21_game(n: int, k: int, maxPts: int) -> float:

Java

public double new21Game(int n, int k, int maxPts)

The intended approach

Time O(n) — one pass with constant work per tally.Space O(n) for the probability table.

Let `chance[t]` be the probability the tally is exactly `t` at some point in the run. A tally of `t` is arrived at from any of the `maxPts` tallies below it that were still under `k` and therefore still dispensing, each with weight one over `maxPts`. Those contributions form a window of fixed width that slides as `t` grows, so keep its sum and adjust it by one addition and one subtraction per step instead of re-adding `maxPts` terms. Tallies of `k` or more are final, so add up the ones that do not exceed `n`. Two shortcuts come first: with `k` equal to zero nothing is dispensed, and once `n` reaches the largest tally the machine could possibly stop on, every outcome qualifies.

Pythonentry point: new21_game

def new21_game(n, k, maxPts):
    # O(n) time, O(n) space: chance[t] is the probability the tally is exactly t
    # at some moment. Reaching t needs a draw from one of the maxPts tallies
    # below it that were still allowed to draw, so chance[t] is the sum of those
    # divided by maxPts. Keeping that sum in a sliding window makes each tally
    # constant work. Tallies from k upward are final and are collected when they
    # are at most n.
    if k == 0 or n >= k - 1 + maxPts:
        return round(1.0, 6)
    chance = [0.0] * (n + 1)
    chance[0] = 1.0
    window = 1.0
    answer = 0.0
    for t in range(1, n + 1):
        chance[t] = window / maxPts
        if t < k:
            window += chance[t]
        else:
            answer += chance[t]
        leaving = t - maxPts
        if leaving >= 0 and leaving < k:
            window -= chance[leaving]
    return round(answer, 6)

The obvious version

Push probability mass forward. Start with all the mass on a tally of 0 and, walking the tallies below `k` in increasing order, spread each tally's mass in equal parts over the `maxPts` tallies it can reach. Since a tally only ever grows, one increasing sweep settles every tally. Then add the mass that came to rest between `k` and `n`.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_new21_game(n, k, maxPts):
    top = k + maxPts
    mass = [0.0] * (top + 1)
    mass[0] = 1.0
    for t in range(k):
        here = mass[t]
        if here:
            share = here / maxPts
            for step in range(1, maxPts + 1):
                mass[t + step] += share
    total = 0.0
    hi = n if n < top else top
    for t in range(k, hi + 1):
        total += mass[t]
    return round(total, 6)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in