Thinking about this as a tree problem is a red-herring, it's really a directed graph. But forget all about that.
Think of a glass anywhere below the top one. It will have one or two glasses above it that can overflow into it. With the appropriate choice of coordinate system (don't worry, see the end) we can write a function to get the "parent" glasses for any given glass.
Now we can think about an algorithm to get the amount of liquid poured into a glass, irrespective of overflow from that glass. The answer is however much liquid is poured into each parent minus the amount stored in each parent glass, divided by 2. Just sum that for all parents. Writing this as a python fragment of the body of an amount_poured_into() function:
# p is coords of the current glass
amount_in = 0
for pp in parents(p):
amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)
The max() is to ensure we don't get a negative amount of overflow.
We are almost finished! We choose a coordinate system with 'y' down the page, first row glasses is 0, second row is 1, etc. The 'x' coordinates have a zero under the top row glass and the second row have x coordinates of -1 and +1, third row -2, 0, +2, and so on. The important point is that the left or right-most glass in level y will have abs(x) = y.
Wrapping all that up into python (2.x), we have:
def parents(p):
"""Get parents of glass at p"""
(x, y) = p
py = y - 1 # parent y
ppx = x + 1 # right parent x
pmx = x - 1 # left parent x
if abs(ppx) > py:
return ((pmx,py),)
if abs(pmx) > py:
return ((ppx,py),)
return ((pmx,py), (ppx,py))
def amount_poured_into(total, p):
"""Amount of fluid poured into glass 'p'"""
(x, y) = p
if y == 0: # ie, is this the top glass?
return total
amount_in = 0
for pp in parents(p):
amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)
return amount_in
def amount_in(total, p):
"""Amount of fluid left in glass p"""
return min(amount_poured_into(total, p), 1)
So to get the amount actually in a glass at p, use amount_in(total, p).
It's not clear from the OP, but the bit about "you cant add parameters" may mean the original question has to be answered in terms of the glass numbers shown. This is solved by writing a mapping function from the show glass numbers to the internal coordinate system used above. It's fiddly, but either an iterative or mathematical solution can be used. An easy to understand iterative function:
def p_from_n(n):
"""Get internal coords from glass 'number'"""
for (y, width) in enumerate(xrange(1, n+1)):
if n > width:
n -= width
else:
x = -y + 2*(n-1)
return (x, y)
Now just rewrite the amount_in() function above to accept a glass number:
def amount_in(total, n):
"""Amount of fluid left in glass number n"""
p = p_from_n(n)
return min(amount_poured_into(total, p), 1)
