aboutsummaryrefslogtreecommitdiff
path: root/champagne_tower.c
diff options
context:
space:
mode:
Diffstat (limited to 'champagne_tower.c')
-rw-r--r--champagne_tower.c41
1 files changed, 41 insertions, 0 deletions
diff --git a/champagne_tower.c b/champagne_tower.c
new file mode 100644
index 0000000..0c3f772
--- /dev/null
+++ b/champagne_tower.c
@@ -0,0 +1,41 @@
+// 799. Champagne Tower
+#include <stdio.h>
+
+/*
+ * we stack glasses in a pyramid, where the first row has 1 glass, the second
+ * row has 2 glasses, and so on until the 100th row. each glass holds one cup of
+ * champagne. then, some champagne is poured into the first glass at the top.
+ * when the topmost glass is full, any excess liquid poured will fall equally to
+ * the glass immediately to the right and left of it. when those glasses become
+ * full, any excess champange will fall equally to the left and right of those
+ * glasses, and so on. (a glass at the bottom row has its excess champagne fall
+ * on the floor). for example, after one cup of champagne is poured, the top
+ * most glass is full. after cups of champagne is poured, the two glasses on the
+ * second row are half full. after three cups are poured, those two cups become
+ * full - there are three glasses total full now. now after pouring some
+ * non-negative integer cups of champagne, return how full the j'th glass in the
+ * i'th row is.
+ */
+
+double champagneTower(int poured, int query_row, int query_glass) {
+ double rem[query_row + 1][query_row + 1];
+ for (int i = 0; i < query_row; i++)
+ for (int j = 0; j < query_row; j++)
+ rem[i][j] = 0;
+ rem[0][0] = poured;
+ for (int i = 1; i <= query_row; i++) {
+ rem[i][0] = (rem[i - 1][0] >= 1) ? ((rem[i - 1][0] - 1) * 0.5) : 0;
+ rem[i][i] = (rem[i - 1][i - 1] >= 1) ? ((rem[i - 1][i - 1] - 1) * 0.5) : 0;
+ for (int j = 1; j < i; j++)
+ rem[i][j] =
+ ((rem[i - 1][j - 1] >= 1) ? ((rem[i - 1][j - 1] - 1) * 0.5) : 0) +
+ ((rem[i - 1][j] >= 1) ? ((rem[i - 1][j] - 1) * 0.5) : 0);
+ }
+ return (rem[query_row][query_glass] > 1) ? 1 : rem[query_row][query_glass];
+}
+
+int main() {
+ printf("%f\n", champagneTower(1, 1, 1)); // expect: 0.00000
+ printf("%f\n", champagneTower(2, 1, 1)); // expect: 0.50000
+ printf("%f\n", champagneTower(100000009, 33, 17)); // expect: 1.00000
+}