diff options
Diffstat (limited to 'champagne_tower.c')
-rw-r--r-- | champagne_tower.c | 41 |
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 +} |