Pensare a questo come a un problema di albero è un'aringa rossa, è davvero un grafico diretto. Ma dimentica tutto.
Pensa a un bicchiere ovunque sotto quello superiore. Avrà uno o due bicchieri sopra di esso che possono traboccare in esso. Con la scelta appropriata del sistema di coordinate (non preoccuparti, vedi la fine) possiamo scrivere una funzione per ottenere gli occhiali "genitori" per ogni vetro dato.
Ora possiamo pensare ad un algoritmo per ottenere la quantità di liquido versato in un bicchiere, indipendentemente dal trabocco dal vetro. La risposta è comunque che molto liquido viene versato in ciascun genitore meno la quantità immagazzinata in ciascun bicchiere di genitori, divisa per 2. Somma somma per tutti i genitori. Scrivendolo come un frammento di python del corpo di una funzione amount_poured_into ():
# 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)
Il max () serve a garantire che non si verifichi una quantità negativa di overflow.
Abbiamo quasi finito! Scegliamo un sistema di coordinate con 'y' in fondo alla pagina, gli occhiali di prima fila sono 0, la seconda fila è 1, ecc. Le coordinate 'x' hanno uno zero sotto il vetro della riga superiore e la seconda fila hanno coordinate x di -1 e +1, terza riga -2, 0, +2 e così via. Il punto importante è che il vetro di sinistra o di destra del livello y avrà abs (x) = y.
Comprendendo tutto ciò in python (2.x), abbiamo:
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)
Quindi per ottenere la quantità effettivamente in un bicchiere in p, usa amount_in (total, p).
Non è chiaro dall'OP, ma il bit su "non puoi aggiungere parametri" può significare che la domanda originale deve essere risolta in termini di numeri di vetro mostrati. Questo è risolto scrivendo una funzione di mappatura dai numeri del vetrino al sistema di coordinate interno usato sopra. È laborioso, ma può essere utilizzata una soluzione iterativa o matematica. Una funzione iterativa di facile comprensione:
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)
Ora basta riscrivere la funzione amount_in () sopra per accettare un numero di vetro:
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)
