Sorry. Small mistake. First test should have been > W(n,k) = (k < 1 || k > n) ? 0 :
This is fixed below. On Sep 16, 4:48 am, Gene <[email protected]> wrote: > My guess is that the "and so on..." means we should be able to solve > this assuming the pyramid is as high as it needs to be in order not > to > overflow. > > With this the problem gets more interesting. I worked it out a bit > farther: > > L/C --- Filled cups > 1 --- 1 > 3 --- 2,3 > 5 --- 5 > 7 --- 4-6 > 8 1/3 --- 8,9 > 11 --- 13 > 13 2/3 --- 12, 14 > 15 --- 7,10 > > At this point, 17,20 are 1/8 full and 18,19 are 7/8 full. 11,15 are > empty but beginning to receive water. > > After looking at the cockeyed for a while I think it's a simple > dynamic program: > > First let's number the cups differently with pairs (n, k) where n is > the level number -- top is n=1 -- and k is the ordinal within a level > -- left is k=1. So > at every level n you have (n,1)(n,2) ... (n,n). Note that n(n-1)/2+k > gives the numbering in the original problem, so it's easy to convert. > > Let W(n,k) be the amount of water that flowed into cup (n,k) after L > has been poured in at the top. Then > > W(n,k) = (k < 1 || k > n) ? 0 : > (n == 1) ? L : > max(0, (W(n - 1, k - 1) - C) / 2) + max(0, (W(n - 1, k) - > C) / 2) > > The last line says that the amount that flowed into this cup is equal > to what's flowed out of the two parents. In turn, what flowed out of a > parent is half of what flowed in after its capacity C was filled. Of > course if that's a negative amount, it's corrected to 0. > > The answer to the final question of how much water is in cup (n,k) > after L has been poured into the top cup is > > W(n,k) > C ? C : W(n,k) > > On Sep 10, 2:42 pm, Dave <[email protected]> wrote: > > > > > @Ishan: Here is the algorithm: > > > If L <= C, then > > cup1 = L > > cup2 = cup3 = cup4 = cup5 = cup6 = overflow = 0 > > else if L < 3*C, then > > cup1 = C > > cup2 = cup3 = (L-C)/2 > > cup4 = cup5 = cup6 = overflow = 0 > > else if L < 5*C, then > > cup1 = cup2 = cup3 = C > > cup4 = cup6 = (L-3*C)/4 > > cup5 = (L-3*C)/2 > > overflow = 0 > > else if L < 7*C, then > > cup1 = cup2 = cup3 = cup5 = C > > cup4 = cup6 = (L-3*C)/4 > > overflow = (L-5*C)/2 > > else if L >= 7*C, then > > cup1 = cup2 = cup3 = cup4 = cup5 = cup6 = C > > overflow = L-6*C > > > And so on. > > > Dave > > > On Sep 10, 9:40 am, Ishan Aggarwal <[email protected]> > > wrote: > > > > 1.) > > > > there is apyramidwith 1 cup at level , 2 at level 2 , 3 at level 3 and so > > > on.. > > > It looks something like this > > > 1 > > > 2 3 > > > 4 5 6 > > > every cup has capacity C. you pour L liters of water from top . when cup 1 > > > gets filled , it overflows to cup 2,3 equally, and when they get filled , > > > Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both > > > the > > > cups and so on. > > > Now given C and M .Find the amount of water in ith cup. > > > > -- > > > Kind Regards > > > Ishan Aggarwal > > > [image: Aricent Group] > > > Presidency Tower-A, M.G.Road,Sector-14 > > > Gurgaon,Haryana.122015 INDIA > > > Phone : +91-9654602663 > > > [email protected] <[email protected]> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
