Show problems as
Classic problem #799MediumDynamic Programming

Champagne Tower

Real-world version: How Full One Glass in the Stack Gets
Tracked in this browser only
Read Champagne Tower on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def champagne_tower(poured: int, row: int, glass: int) -> float:
Java
public double champagneTower(int poured, int row, int glass)

More on the same topics