1017MediumDynamic Programming

How Full One Glass in the Stack Gets

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.

Glasses are stacked in rows: one on the top row, two on the row below, three on the row below that, and so on. Every glass holds one measure when full.

Each glass rests so that anything overflowing it is shared out evenly between the two glasses directly beneath, one to its left and one to its right. Overflow running off either end of a row spills to the floor and is gone.

poured measures are poured into the top glass. Once everything has settled, return how full the glass sitting at position glass along row row is, counting the top glass as row 0 and counting the glasses along each row from 0.

Examples

Example 1

Input: poured = 2, row = 1, glass = 1
Output: 0.5

Two measures fill the top glass and leave one over, which shares evenly between the two glasses beneath, so each of them holds half a measure.

Example 2

Input: poured = 1, row = 1, glass = 0
Output: 0.0

One measure fills the top glass exactly, with nothing left to overflow, so the row below stays dry.

Example 3

Input: poured = 987654321, row = 33, glass = 17
Output: 1.0

The first thirty-four rows hold five hundred and ninety-five measures between them, and far more than that is poured, so every glass in them is full.

Constraints

0 <= poured <= 10^9
0 <= row <= 99
0 <= glass <= row

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 champagne_tower(poured: int, row: int, glass: int) -> float:

Java

public double champagneTower(int poured, int row, int glass)

The intended approach

Time O(r^2) for the wanted row r, since each of the first r rows holds at most r glasses.Space O(r) for the two rows held.

Track, row by row, how much each glass received rather than how much it kept. The top glass receives everything poured. Whatever a glass received, it keeps the smaller of that and one measure, and passes on whatever is over one measure, halved into each of the two glasses beneath it. So carry the received amounts for the row in hand, and build the row below by taking each glass's overflow, halving it, and adding that into the two places under it. A glass that received a measure or less passes nothing on. Stop once the wanted row has been built, then cap that glass's received amount at one measure and report it. Rows stop below a hundred, so at most a hundred rows of at most a hundred glasses are ever touched, and only the row in hand and the one being built need holding at once. Pouring a billion measures is no harder than pouring one: the overflow halves at each step, so amounts thin out quickly down the stack, but nothing in the sweep leans on that.

Pythonentry point: champagne_tower

def champagne_tower(poured, row, glass):
    current = [float(poured)]
    for _ in range(row):
        nxt = [0.0] * (len(current) + 1)
        for at in range(len(current)):
            spare = (current[at] - 1.0) / 2.0
            if spare > 0.0:
                nxt[at] += spare
                nxt[at + 1] += spare
        current = nxt
    got = current[glass]
    return got if got < 1.0 else 1.0

The obvious version

Lay out the whole triangle of received amounts down to the wanted row and fill it in from the top, pushing each glass's overflow into the two places below as it goes, then read off the wanted glass and cap it at a measure. Holds every row at once instead of only the one in hand.

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_champagne_tower(poured, row, glass):
    table = [[0.0] * (r + 1) for r in range(row + 1)]
    table[0][0] = float(poured)
    for r in range(row):
        for c in range(r + 1):
            over = table[r][c] - 1.0
            if over > 0.0:
                table[r + 1][c] += over / 2.0
                table[r + 1][c + 1] += over / 2.0
    got = table[row][glass]
    return got if got < 1.0 else 1.0

How this problem was checked

Reference solution executed against 16 test cases — 16 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