I always wanted to know if there is any real-world application of Pascal's triangle than just coefficients of the binomial expansion.
I tried to solve this problem:
But, What if I am adding K units of water and wants to find a glass which has the least water in it:
Where, Glass will be found as: c-th glass in r-th row
And I believe. If we could find this then it will not be difficult for us to find amount of water in any glass for which {i<r and j<c}
Problem:
Input Water added- K units and capacity of each glass as 1- unit
Output Expected :
cth glass inrth row having least water in it.
I tried to solve problem by keeping note of capacity of each row when it starts overflow: and wants to know how to keep going with this method.
1 max = 1, cap = 1
1 1 max = 1, sum(coefficients)=2**1 = 2, cap = 2/1
1 2 1 max = 2, sum = 2**2, cap = 4/2 = 2 units
1 3 3 1 max = 3, sum = 2**3, cap = 8/3 units
1 4 6 4 1 max = 6, sum = 2**4, cap = 16/6 units
#Not sure but this is how it seems to me for the rate @which water is being added.
1
1/2 1/2
1/4 2/4 1/4
1/8 3/8 3/8 1/8
1/16 4/16 6/16 4/16 1/16
Should I use 2-D list and define as :
Δ1, Δ2 = 0, 0
if g(n-1, k)>1 and k <= n-1:
Δ1 = g(n-1, k) -1
if g(n-1, k-1)>1 and k-1 <= n-1:
Δ2 = g(n-1, k-1) - 1
g(n, k) = Δ1/2 Δ2/2
g(n,k) = g(n-1, k-1) g(n-1, k)
g = [[0]*(i 1) for i in range(11)]
def f(g, K):
g[1][1] = 1
K = K-1
d1, d2 = 0, 0
for n in range(2, 10):
for k in range(1, n 1):
if k ==1:
g[n][k] = g[n-1][k]/2
if k == n:
g[n][k] = g[n-1][k-1]/2
else:
if g[n-1][k-1]>1:
d1 = g[n-1][k-1] -1
if g[n-1][k] > 1:
d2 = g[n-1][k] -1
g[n][k] = d1/2 d2/2
return g, K
k = int(input())
while k:
g, k = f(g, k)
for x in g:
print(x)
I don't know what is missing?
CodePudding user response：
For such small K constraint simple row-by-row filling is enough (we can store only two rows, here 2D list is used for simplicity)
def fillGlasses(k, row, col):
gl = [[k]]
level = 1
overflow_occured = True
while overflow_occured: # also can stop when at needed row
print(gl[level-1]) #before overflow
level = 1
overflow_occured = False
gl.append([0]*level)
for i in range(level - 1):
t = gl[level-2][i] - 1
if t > 0:
gl[level-1][i] = t/2
gl[level-1][i 1] = t/2
gl[level-2][i] = 1
overflow_occured = True
#print(gl) #after all
return gl[row-1][col-1]
print(fillGlasses(21,8,4))
[21]
[10.0, 10.0]
[4.5, 9.0, 4.5]
[1.75, 5.75, 5.75, 1.75]
[0.375, 2.75, 4.75, 2.75, 0.375]
[0, 0.875, 2.75, 2.75, 0.875, 0]
[0, 0, 0.875, 1.75, 0.875, 0, 0]
[0, 0, 0, 0.375, 0.375, 0, 0, 0]
0.375
CodePudding user response：
I presumed you are asking this exact online judge question, or a very similar one: https://practice.geeksforgeeks.org/problems/champagne-overflow2636/1
If so, actually the constraints for R and C is only 500 and any simulation could work. One little catch is that there maybe water in a row even previous row is not fully filled. You may consider small test cases and simulate to find out, for example K = 6, the glasses will look like:
1
1, 1
0.75, 1, 0.75
0, 0.25, 0.25, 0
// Notice previous row is not fully filled, makes sense as "middle" glasses will overflow faster
I think for implementation-wise it is similar for top-down and bottom-up approach. Here is my top-down accepted code which simply simulate the water pouring and overflow process, with C , same algorithm can be implemented in any language:
class Solution {
public:
double cups[505][505];
void pourWaterAt(double K, int R, int C, int targetR){
if(R > targetR) return;
cups[R][C] = K;
if(cups[R][C] > 1){
double overflow = cups[R][C] - 1;
cups[R][C] = 1;
pourWaterAt(overflow/2.0f, R 1, C, targetR);
pourWaterAt(overflow/2.0f, R 1, C 1, targetR);
}
}
double waterOverflow(int K, int R, int C) {
memset(cups, 0, sizeof(cups));
pourWaterAt(K, 1, 1, R);
return cups[R][C];
}
};
After the simulation, you can just scan through cups[R][C] and find the smallest positive one (and its index) to get the answer.