Champagne Tower

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100^th row. Each glass holds one cup of champagne.

Some champagne is poured into the first glass at the top. When a glass becomes full, any excess liquid poured into it falls equally to the glass immediately to the left and right of it in the next row. When those glasses become full, any excess champagne similarly falls equally to their left and right, and so on. A glass at the bottom row has its excess champagne fall on the floor.

After pouring some non-negative integer cups of champagne, return how full the j^th glass in the i^th row is, where both i and j are 0-indexed. The inputs are poured, query_row, and query_glass, and the returned value should be between 0 and 1 inclusive.

Example 1
Inputpoured = 1, query_row = 1, query_glass = 1
Output0
We poured 1 cup of champagne to the top glass of the tower, so there is no excess liquid and all glasses below it remain empty.
Example 2
Inputpoured = 2, query_row = 1, query_glass = 1
Output0.5
The one cup of excess liquid from the top glass is shared equally by glasses (1, 0) and (1, 1), so the queried glass gets half a cup.

Constraints

  • 0 <= poured <= 10^9
  • 0 <= query_glass <= query_row < 100

Asked at 6 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate