Lemonade Glass Pyramid

Medium

Glasses are stacked in a pyramid: one glass in the top row, two in the second, three in the third and so on, 100 rows in total. Each glass holds exactly one cup. cups cups of lemonade are poured into the top glass. Once a glass is full, whatever keeps flowing into it spills evenly into the two glasses below it, left and right. Overflow from the bottom row lands on the floor. Return how full glass number glass in row row is (both 0-based), as a number from 0 to 1.

Example 1

cups=3, row=1, glass=0 → 1.0

The top glass takes the first cup, the other two split evenly between the two glasses of the second row, so both are full.

Example 2

cups=4, row=2, glass=0 → 0.25

Each glass of the second row receives 1.5 cups, and each excess of 0.5 splits in two. The edge glass of the third row gets 0.25.

Example 3

cups=1, row=3, glass=2 → 0

One cup stays entirely in the top glass; nothing reaches lower rows.

Constraints

0 ≤ cups ≤ 10⁹
0 ≤ glass ≤ row < 100
Answers within 10⁻⁶ are accepted

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium

Input

cups=3, row=1, glass=0

Expected

1.0

Run checks the first 3 tests in your browser. Submit checks all 186 tests on the server, hidden ones included.