# https://leetcode.com/explore/challenge/card/october-leetcoding-challenge/562/week-4-october-22nd-october-28th/3508/
# https://leetcode.com/problems/champagne-tower/
#
# We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, 
# and so on until the 100th row.  Each glass holds one cup of champagne.

# Then, some champagne is poured into the first glass at the top.  When the topmost glass is full, 
# any excess liquid poured will fall equally to the glass immediately to the left and right of it.  
# When those glasses become full, any excess champagne will fall equally to the left and right of 
# those glasses, and so on.  (A glass at the bottom row has its excess champagne fall on the floor.)

# For example, after one cup of champagne is poured, the top most glass is full.  After two cups 
# of champagne are poured, the two glasses on the second row are half full.  After three cups of 
# champagne are poured, those two cups become full - there are 3 full glasses total now.  After 
# four cups of champagne are poured, the third row has the middle glass half full, and the two 
# outside glasses are a quarter full, as pictured below.

# Now after pouring some non-negative integer cups of champagne, return how full the jth glass 
# in the ith row is (both i and j are 0-indexed.)

# Example 1:
#     Input: poured = 1, query_row = 1, query_glass = 1
#     Output: 0.00000
#     Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). 
#         There will be no excess liquid so all the glasses under the top glass will remain empty.
# Example 2:
#     Input: poured = 2, query_row = 1, query_glass = 1
#     Output: 0.50000
#     Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). 
#         There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will
#         share the excess liquid equally, and each will get half cup of champange.
# Example 3:
#     Input: poured = 100000009, query_row = 33, query_glass = 17
#     Output: 1.00000
# Constraints:
#     0 <= poured <= 109
#     0 <= query_glass <= query_row < 100

# from typing import List
class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        # A = [[0] * k for k in range(1, 102)]
        # A[0][0] = poured
        # for r in range(query_row + 1):
        #     for c in range(r+1):
        #         q = (A[r][c] - 1.0) / 2.0
        #         if q > 0:
        #             A[r+1][c] += q
        #             A[r+1][c+1] += q

        # return min(1, A[query_row][query_glass])
        
        if poured is None or poured == 0:
            return 0.0000
        elif query_row is None or query_glass is None:
            return 0.0000
        debug = True
        totalGlasses = 0
        leftToPour = poured
        i = 0
        # for i in range(query_row):
        while True:
            totalGlasses += (i + 1)
            leftToPour -= totalGlasses
            if leftToPour == 0:
                return 0.0000
            
            if i == query_row:
                if leftToPour >= i:
                    return 1.0000
                if debug: print('found query_row = %s with totalGlasses = %s of poured %s' % (query_row, totalGlasses, poured))
                # cupPartials = (totalGlasses - poured) / i
                cupPartials = (poured - (totalGlasses - i + 1)) / i
                if debug: print('cupPartials =', cupPartials)
                if query_glass == 0 or query_glass == i:
                    if debug: print('found cup index 0 or i =', i)
                    return cupPartials / 2
                else:
                    if debug: print('found middle cup')
                    return cupPartials
            i += 1

s = Solution()
# input_val1 = 1
# input_val2 = 1
# input_val3 = 1
# solution = 0.0000
# output = s.champagneTower(input_val1, input_val2, input_val3)
# print("%s | %s" % ('PASS' if (output == solution) else 'FAIL', output))

# input_val1 = 2
# input_val2 = 1
# input_val3 = 1
# solution = 0.5000
# output = s.champagneTower(input_val1, input_val2, input_val3)
# print("%s | %s" % ('PASS' if (output == solution) else 'FAIL', output))

# input_val1 = 100000009
# input_val2 = 33
# input_val3 = 17
# solution = 1.0000
# output = s.champagneTower(input_val1, input_val2, input_val3)
# print("%s | %s" % ('PASS' if (output == solution) else 'FAIL', output))

input_val1 = 25
input_val2 = 6
input_val3 = 1
solution = 0.18750
output = s.champagneTower(input_val1, input_val2, input_val3)
print("%s | %s" % ('PASS' if (output == solution) else 'FAIL', output))
