Champagne Tower
Problem
Pour poured cups into the top glass of a tower; once a glass holds more than 1 cup the excess splits evenly into the two glasses below. Return how full glass (query_row, query_glass) is, capped at 1.
poured = 2, query_row = 1, query_glass = 10.5def champagne_tower(poured, query_row, query_glass):
row = [poured]
for r in range(query_row):
nxt = [0.0] * (r + 2)
for i, v in enumerate(row):
if v > 1:
spill = (v - 1) / 2
nxt[i] += spill
nxt[i + 1] += spill
row = nxt
return min(1.0, row[query_glass])function champagneTower(poured, query_row, query_glass) {
let row = [poured];
for (let r = 0; r < query_row; r++) {
const next = new Array(r + 2).fill(0);
for (let i = 0; i < row.length; i++) {
if (row[i] > 1) {
const spill = (row[i] - 1) / 2;
next[i] += spill;
next[i + 1] += spill;
}
}
row = next;
}
return Math.min(1, row[query_glass]);
}class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] row = new double[]{ poured };
for (int r = 0; r < query_row; r++) {
double[] next = new double[r + 2];
for (int i = 0; i < row.length; i++) {
if (row[i] > 1) {
double spill = (row[i] - 1) / 2.0;
next[i] += spill;
next[i + 1] += spill;
}
}
row = next;
}
return Math.min(1.0, row[query_glass]);
}
}class Solution {
public:
double champagneTower(int poured, int query_row, int query_glass) {
vector<double> row = { (double)poured };
for (int r = 0; r < query_row; r++) {
vector<double> next(r + 2, 0.0);
for (int i = 0; i < (int)row.size(); i++) {
if (row[i] > 1) {
double spill = (row[i] - 1) / 2.0;
next[i] += spill;
next[i + 1] += spill;
}
}
row = next;
}
return min(1.0, row[query_glass]);
}
};Explanation
Rather than do clever math, we just simulate the pour one row at a time. Each glass can hold at most 1 cup; anything above that overflows and splits evenly into the two glasses directly below it.
We start with a single-element row row = [poured] representing the top glass. Then we repeat the overflow step until we reach the row we care about, query_row.
For each glass i in the current row, if it holds more than 1 we compute spill = (v - 1) / 2 and add that amount to both children in the next row: next[i] and next[i + 1]. Glasses holding 1 or less spill nothing.
After processing query_row rows, the value in row[query_glass] is how much liquid arrived there. Since a glass can't show more than full, we return min(1.0, row[query_glass]).
Example: poured = 2. The top glass overflows 2 - 1 = 1 cup, split as 0.5 and 0.5 into row 1. So glass (1, 1) holds 0.5.