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) ? 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.
