509. Champagne Tower
Picture a pyramid of champagne glasses: row 0 holds one glass, row 1 holds two, row 2 holds three, and so on for 100 rows. Every glass holds exactly one cup. You pour poured cups into the top glass. The moment any glass has taken in more than one cup, the excess splits evenly between the two glasses diagonally beneath it; champagne falling past the bottom row is lost.
Your function receives the integers poured, query_row, and query_glass (both 0-indexed) and must return how full glass number query_glass in row query_row ends up — a value between 0.0 (empty) and 1.0 (full).
Canonical output: your return value is printed with exactly five digits after the decimal point.
Example 1:
Input: poured = 1, query_row = 1, query_glass = 1
Output: 0.00000
Explanation: One cup exactly fills the top glass, so nothing overflows and every glass in row 1 stays empty.
Example 2:
Input: poured = 2, query_row = 1, query_glass = 1
Output: 0.50000
Explanation: The top glass keeps one cup and spills the other; the excess splits evenly, so each glass in row 1 receives half a cup.
Constraints:
- 0 ≤ poured ≤ 10⁹
- 0 ≤ query_glass ≤ query_row ≤ 99
Hints:
Don't track fullness directly — track the total amount that *flows into* each glass. A glass's fullness is simply min(1, flow); clamping earlier loses the overflow information.
Row r + 1 depends only on row r: every glass with flow f > 1 sends (f − 1) / 2 to positions c and c + 1 below it. Simulate one row at a time down to query_row.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: poured = 1, query_row = 1, query_glass = 1
Expected output: 0.00000