Saturday, December 24, 2011

Water Cup Pyramid Problem.

There is a pyramid with 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 L .Find the amount of water in kth cup.


Idea:
Pour L into coup 1. Divide into its children if overflows. Do this for subsequent elements, until find k.
LeftChildIndex = index + height[index] + 1 for the first child,
RightchildIndex = LeftChildIndex  + 1 for the next.


Suppose C=3.0 and L=23.0 then lets find out the amount of water in 8th Cup.
OutPut:

CUP: 1 :H: 0 :W: 3.0
CUP: 2 :H: 1 :W: 3.0
CUP: 3 :H: 1 :W: 3.0
CUP: 4 :H: 2 :W: 3.0
CUP: 5 :H: 2 :W: 3.0
CUP: 6 :H: 2 :W: 3.0
CUP: 7 :H: 3 :W: 0.25
CUP: 8 :H: 3 :W: 2.25
Water Amount in 8th cup: 2.25





No comments:

Post a Comment