leetcode

commit 902d9459f6cd4e135401feb842fb2318dedd1360
parent 233d96e7ac7b11b25daf1c495e424da228257387
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 13 Feb 2026 21:38:00 -0700

799. champagne tower

Diffstat:
M
champagne_tower.c
 | 
38
+++++++++++++++++++++-----------------
M
champagne_tower.py
 | 
20
+++++++++++---------

2 files changed, 32 insertions(+), 26 deletions(-)
diff --git a/champagne_tower.c b/champagne_tower.c
@@ -1,5 +1,5 @@
 // 799. Champagne Tower
-#include <stdio.h>
+#include "leetcode.h"
 
 /*
  * we stack glasses in a pyramid, where the first row has 1 glass, the second
@@ -18,24 +18,28 @@
  */
 
 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);
+  double flow[102][102] = {0.0};
+  flow[0][0] = (double)poured;
+  for (int r = 0; r <= query_row; ++r) {
+    for (int c = 0; c <= r; ++c) {
+      double q = (flow[r][c] - 1.0) / 2.0;
+      if (q > 0) {
+        flow[r + 1][c] += q;
+        flow[r + 1][c + 1] += q;
+      }
+    }
   }
-  return (rem[query_row][query_glass] > 1) ? 1 : rem[query_row][query_glass];
+  return fmin(1.0, flow[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
+  double r1 = champagneTower(1, 1, 1);
+  double r2 = champagneTower(2, 1, 1);
+  double r3 = champagneTower(100000009, 33, 17);
+  printf("%f\n", r1); // expect: 0.00000
+  assert(r1 == 0.00000);
+  printf("%f\n", r2); // expect: 0.50000
+  assert(r2 == 0.50000);
+  printf("%f\n", r3); // expect: 1.00000
+  assert(r3 == 1.00000);
 }
diff --git a/champagne_tower.py b/champagne_tower.py
@@ -19,15 +19,17 @@ i'th row is.
 
 class Solution(object):
     def champagneTower(self, poured, query_row, query_glass):
-        tower = [[0] * (i + 1) for i in range(query_row + 1)]
-        tower[0][0] = poured
-        for row in range(query_row):
-            for glass in range(len(tower[row])):
-                execess = (tower[row][glass] - 1) / 2.0
-                if execess > 0:
-                    tower[row + 1][glass] += execess
-                    tower[row + 1][glass + 1] += execess
-        return min(1.0, tower[query_row][query_glass])
+        """
+        :type poured: int
+        :type query_row: int
+        :type query_glass: int
+        :rtype: float
+        """
+        flow = [poured] + [0] * query_row
+        for r in range(1, query_row + 1):
+            for c in range(r, -1, -1):
+                flow[c] = max(flow[c] - 1, 0) / 2.0 + max(flow[c - 1] - 1, 0) / 2.0
+        return min(flow[query_glass], 1.0)
 
 
 if __name__ == "__main__":