There is a stack of water glasses in a form of pascal triangle and a person wants to pour the water at the topmost glass, but the capacity of each glass is 1 unit. Overflow takes place in such a way that after 1 unit, 1/2 of remaining unit gets into bottom left glass and other half in bottom right glass.Now John pours K units of water in the topmost glass and wants to know how much water is there in the Cth glass of the Rth row.
Note: Assume that there are enough glasses in the triangle till no glass overflows.
 
Example 1:
Input:
K = 3, R = 2, C = 1
Output:
1.000000
Explanation:
After the first glass, 2 units of water
will remain and they will spread equally
on the two glasses on the second row.
Therefore, the glass on the 2nd row and
1st column will have 1 unit of water.
Example 2:
Input:
K = 3, R = 2, C = 2
Output:
1.000000
Explanation:
After the first glass, 2 units of water
will remain and they will spread equally
on the two glasses on the second row.
Therefore, the glass on the 2nd row and
2nd column will have 1 unit of water.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function waterOverflow() which takes 3 Integers K, R and C as input and returns the amount of water(6 digits of precision) in the Cth glass of Rth row.
 
Expected Time Complexity: O(K^{2})
Expected Auxiliary Space: O(K^{2})
 
Constraints:
1 <= K <= 500
1 <= R,C <= K

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def waterOverflow(self, K, R, C):

        # code here 

Solutions:
class Solution:

	def waterOverflow(self, K, R, C):
		dp = [[0 for j in range(K + 1)] for i in range(K + 1)]
		dp[0][0] = K
		for i in range(K):
			for j in range(i + 1):
				if dp[i][j] > 1.0:
					rem = dp[i][j] - 1.0
					dp[i][j] = 1.0
					dp[i + 1][j] += rem / 2.0
					dp[i + 1][j + 1] += rem / 2.0
		return '{:.6f}'.format(dp[R - 1][C - 1])


class Solution:

	def waterOverflow(self, K, R, C):
		(prev, cur) = ([K], None)
		for _ in range(1, R):
			cur = [0] * (len(prev) + 1)
			for (i, v) in enumerate(prev):
				if v > 1:
					add = (v - 1) / 2
					cur[i] += add
					cur[i + 1] += add
			prev = cur
		ans = min(1.0, prev[C - 1])
		return '{:.6f}'.format(ans)


class Solution:

	def waterOverflow(self, K, R, C):
		dp = [K]
		for i in range(2, R + 1):
			ndp = [0] * i
			for j in range(i - 1):
				if dp[j] > 1:
					p = (dp[j] - 1) / 2
					ndp[j] += p
					ndp[j + 1] += p
			dp = ndp
		if dp[C - 1] >= 1:
			return '%.6f' % 1.0
		return '%.6f' % dp[C - 1]


class Solution:

	def waterOverflow(self, k, R, C):
		if R == 1:
			return '1.000000' if k else '0.000000'
		glass = [0] * (R * (R + 1) // 2)
		index = 0
		glass[index] = float(k)
		for i in range(1, R):
			for j in range(i):
				if glass[index] > 1:
					extra = glass[index] - 1
					glass[index] = float(1)
					glass[index + i] += extra / 2
					glass[index + i + 1] += extra / 2
				index += 1
		ans = glass[R * (R - 1) // 2 + C - 1]
		if ans >= 1:
			return '1.000000'
		ans = format(ans, '.6f')
		return ans


class Solution:

	def waterOverflow(self, K, R, C):
		dp = [[0] * (K + 1) for i in range(K + 1)]
		dp[1][1] = K
		for i in range(1, K):
			for j in range(1, i + 1):
				if dp[i][j] > 1:
					dp[i + 1][j] += (dp[i][j] - 1) / 2
					dp[i + 1][j + 1] += (dp[i][j] - 1) / 2
					dp[i][j] = 1
		if dp[R][C] >= 1:
			return 1
		return round(dp[R][C], 6)


class Solution:

	def waterOverflow(self, k, r, c):
		z = [k]
		for i in range(r - 1):
			q = [0] * (len(z) + 1)
			for j in range(len(z)):
				a = max(0, (z[j] - 1) / 2)
				q[j] += a
				q[j + 1] += a
			z = q
		return round(min(1, z[c - 1]), 6)


from decimal import Decimal

class Solution:

	def waterOverflow(self, K, R, C):
		dp = [[0 for _ in range(K)] for _ in range(K)]
		dp[0][0] = K
		t = K
		for i in range(K):
			for j in range(K):
				if dp[i][j] > 1:
					spare = dp[i][j] - 1
					dp[i][j] = 1
					val = spare / 2
					if spare % 2 == 0:
						dp[i + 1][j] += int(val)
						dp[i + 1][j + 1] += int(val)
					else:
						dp[i + 1][j] += val
						dp[i + 1][j + 1] += val
		ans = '{0:.6f}'.format(dp[R - 1][C - 1])
		return Decimal(ans).normalize()


class Solution:

	def waterOverflow(self, k, r, c):
		dp = [[0] * (K + 1) for i in range(K + 1)]
		dp[1][1] = K
		for i in range(1, K):
			for j in range(1, i + 1):
				if dp[i][j] > 1:
					dp[i + 1][j] += (dp[i][j] - 1) / 2
					dp[i + 1][j + 1] += (dp[i][j] - 1) / 2
					dp[i][j] = 1
		if dp[R][C] >= 1:
			return 1
		return round(dp[R][C], 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(K, R, C) = map(int, input().split())
		ob = Solution()
		print(ob.waterOverflow(K, R, C))


class Solution:

	def waterOverflow(self, K, R, C):
		if R == 1:
			if K > 1:
				return 1
			else:
				return K
		arr = [[0] * R for j in range(R)]
		arr[0][0] = K
		for i in range(R - 1):
			for j in range(R - 1):
				if arr[i][j] > 1:
					t = arr[i][j] - 1
					arr[i][j] = 1
					arr[i + 1][j] += t / 2
					arr[i + 1][j + 1] += t / 2
		return min(1, round(arr[R - 1][C - 1], 6))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(K, R, C) = map(int, input().split())
		ob = Solution()
		print(ob.waterOverflow(K, R, C))


class Solution:

	def waterOverflow(self, K, R, C):
		if C > R:
			return 0
		dp = [0] * int(R * (R + 1) / 2)
		idx = 0
		dp[idx] = K
		for i in range(1, R):
			for j in range(1, i + 1):
				X = dp[idx]
				dp[idx] = 1 if X >= 1 else X
				X = X - 1 if X >= 1 else 0
				dp[i + idx] += X / 2
				dp[i + idx + 1] += X / 2
				idx += 1
		if dp[R * (R + 1) // 2 - C] >= 1:
			return 1
		else:
			return round(dp[R * (R + 1) // 2 - C], 6)


class Solution:

	def waterOverflow(self, k, R, C):
		dp = [[0 for i in range(k + 1)] for _ in range(k + 1)]
		dp[0][0] = k
		for i in range(0, k + 1):
			for j in range(0, k + 1):
				if dp[i][j] > 1:
					temp = dp[i][j] - 1
					temp = temp / 2
					dp[i][j] = 1
					dp[i + 1][j] += temp
					dp[i + 1][j + 1] += temp
		return '{:.6f}'.format(dp[R - 1][C - 1]).rstrip('0').rstrip('.')


class Solution:

	def waterOverflow(self, K, R, C):

		def waterLevel(r, c, k):
			if self.water_table[r][c] != -1:
				return self.water_table[r][c]
			if c == 1 and r == 1:
				return max(k, 0)
			if c > r:
				return 0
			if c == r:
				level = max(0, (waterLevel(r - 1, c - 1, k) - 1) / 2)
				self.water_table[r][c] = level
				return level
			if c == 1:
				level = max(0, (waterLevel(r - 1, c, k) - 1) / 2)
				self.water_table[r][c] = level
				return level
			level = max(0, (waterLevel(r - 1, c, k) - 1) / 2) + max(0, (waterLevel(r - 1, c - 1, k) - 1) / 2)
			self.water_table[r][c] = level
			return level
		self.water_table = [[-1 for i in range(501)] for j in range(501)]
		return min(1, round(waterLevel(R, C, K), 6))


class Solution:

	def waterOverflow(self, K, R, C):
		dp = [[0 for _ in range(K + 1)] for _ in range(K + 1)]
		dp[0][0] = K
		for i in range(K + 1):
			for j in range(i + 1):
				if dp[i][j] > 1.0:
					spare = dp[i][j] - 1
					dp[i][j] = 1.0
					dp[i + 1][j] += spare / 2.0
					dp[i + 1][j + 1] += spare / 2.0
		return '{:.6f}'.format(dp[R - 1][C - 1]).rstrip('0').rstrip('.')


class Solution:

	def waterOverflow(self, k, R, C):
		dp = []
		for i in range(k + 1):
			temp = [0] * (k + 1)
			dp.append(temp)
		dp[0][0] = k
		for i in range(k + 1):
			for j in range(k + 1):
				if dp[i][j] > 1.0:
					overflow = dp[i][j] - 1
					dp[i][j] = 1.0
					dp[i + 1][j] += overflow / 2
					dp[i + 1][j + 1] += overflow / 2
		return format(dp[R - 1][C - 1], '.6f')


class Solution:

	def waterOverflow(self, K, R, C):
		m = [[0 for y in range(x + 1)] for x in range(R)]
		m[0][0] = K
		try:
			for i in range(R):
				for j in range(len(m[i])):
					if m[i][j] > 1:
						spare = m[i][j] - 1
						m[i][j] = 1
						m[i + 1][j] = m[i + 1][j] + spare / 2
						m[i + 1][j + 1] = m[i + 1][j + 1] + spare / 2
			return round(m[R - 1][C - 1], 6) if round(m[R - 1][C - 1], 6) < 1 else 1
		except Exception as ex:
			return round(m[R - 1][C - 1], 6) if round(m[R - 1][C - 1], 6) < 1 else 1


class Solution:

	def waterOverflow(self, k, r, c):
		l = [[0 for i in range(k)] for j in range(k)]
		for i in range(r):
			for j in range(k):
				if i == 0:
					l[0][0] = k
					break
				else:
					num = l[i - 1][j] - 1
					half = round(num / 2, 7)
					if num < 0:
						half = 0
					l[i][j] += half
					if j + 1 < k:
						l[i][j + 1] += half
		ans = '{:.6f}'.format(l[r - 1][c - 1])
		ans = float(ans)
		if ans >= 1:
			ans = 1.0
		return ans


class Solution:

	def flowThrough(self, K, R, C):
		if R == 1:
			return K
		(lw, rw) = (0, 0)
		if C - 1 > 0:
			lw = max((self.flowThrough(K, R - 1, C - 1) - 1) / 2, 0)
		if C < R:
			rw = max((self.flowThrough(K, R - 1, C) - 1) / 2, 0)
		return lw + rw

	def waterOverflow(self, K, R, C):
		return '%.6f' % min(self.flowThrough(K, R, C), 1)


class Solution:

	def waterOverflow(self, K, R, C):
		glasses = [[0] * (row + 1) for row in range(R)]
		glasses[0][0] = K
		for r in range(1, len(glasses)):
			for c in range(len(glasses[r])):
				if c == 0:
					left = (glasses[r - 1][0] - 1) / 2
					glasses[r][c] = left if left > 0 else 0
				elif c == len(glasses[r]) - 1:
					right = (glasses[r - 1][-1] - 1) / 2
					glasses[r][c] = right if right > 0 else 0
				else:
					left = (glasses[r - 1][c - 1] - 1) / 2
					right = (glasses[r - 1][c] - 1) / 2
					glasses[r][c] = (left if left > 0 else 0) + (right if right > 0 else 0)
		return '{0:.6f}'.format(1 if glasses[R - 1][C - 1] >= 1 else glasses[R - 1][C - 1])


from math import *
from collections import deque

class Solution:

	def waterOverflow(self, k, R, C):
		h = [[0 for i in range(k + 1)] for j in range(k + 1)]
		h[0][0] = k
		for i in range(k):
			for j in range(i + 1):
				if h[i][j] > 1:
					h[i + 1][j] += (h[i][j] - 1) / 2
					h[i + 1][j + 1] += (h[i][j] - 1) / 2
					h[i][j] = 1
		if h[R - 1][C - 1] >= 1:
			return 1
		return round(h[R - 1][C - 1], 6)


def fillWater(i, j, k):
	dp = [[0 for x in range(k + 1)] for y in range(k + 1)]
	dp[0][0] = k
	for m in range(len(dp)):
		for n in range(m + 1):
			if dp[m][n] > 1:
				s = dp[m][n] - 1
				dp[m][n] = 1
				s = s / 2
				dp[m + 1][n] += s
				dp[m + 1][n + 1] += s
	return round(dp[i - 1][j - 1], 6)

class Solution:

	def waterOverflow(self, K, R, C):
		return fillWater(R, C, K)


class Solution:

	def waterOverflow(self, K, R, C):
		l1 = list()
		for i in range(1, R + 1):
			l2 = [0] * i
			l1.append(l2)
		l1[0][0] = K
		for i in range(len(l1) - 1):
			for j in range(0, len(l1[i])):
				a = l1[i][j]
				if a > 1:
					l1[i + 1][j] = l1[i + 1][j] + (a - 1) / 2
					l1[i + 1][j + 1] = l1[i + 1][j + 1] + (a - 1) / 2
					l1[i][j] = 1
		if l1[R - 1][C - 1] > 1:
			return 1
		return round(l1[R - 1][C - 1], 6)


class Solution:

	def waterOverflow(self, k, r, c):
		dp = [[0 for i in range(r + 1)] for j in range(r + 1)]
		dp[0][0] = k
		for i in range(1, r + 1):
			for j in range(i):
				if dp[i - 1][j] > 1:
					dp[i][j] += (dp[i - 1][j] - 1) / 2
					dp[i][j + 1] += (dp[i - 1][j] - 1) / 2
					dp[i - 1][j] = 1
		return round(dp[r - 1][c - 1], 6)


class Solution:

	def waterOverflow(self, K, R, C):
		dp = [[0 for j in range(i + 1)] for i in range(K)]
		dp[0][0] = K
		out = False
		for i in range(K):
			out = True
			for j in range(i + 1):
				if dp[i][j] > 1:
					out = False
					left = dp[i][j] - 1
					dp[i][j] = 1
					dp[i + 1][j] += left / 2
					dp[i + 1][j + 1] += left / 2
			if out == True:
				break
		return round(dp[R - 1][C - 1], 6)


class Solution:

	def waterOverflow(self, Amount, R, C):
		A = [[0 for i in range(R + 1)] for i in range(R + 1)]
		A[0][0] = Amount
		for i in range(R):
			for j in range(i + 1):
				if A[i][j] > 1:
					x = A[i][j] - 1
					A[i][j] = 1
					A[i + 1][j] += x / 2
					A[i + 1][j + 1] += x / 2
		if A[R - 1][C - 1] == 1:
			return 1
		Water_Amount = round(A[R - 1][C - 1], 6)
		return Water_Amount


class Solution:

	def waterOverflow(self, K, R, C):
		arr = [[K]]

		def all_less(a):
			for i in a:
				if i > 1:
					return False
			return True
		while True:
			if all_less(arr[-1]):
				break
			l = [0]
			x = arr[-1]
			j = 0
			for i in range(len(x)):
				if arr[-1][i] > 1:
					k = arr[-1][i] - 1
					arr[-1][i] = arr[-1][i] - k
					l[j] += k / 2
					l.append(k / 2)
					j += 1
				else:
					l.append(0)
					j += 1
			arr.append(l)
		return '%.6f' % arr[R - 1][C - 1]


class Solution:

	def waterOverflow(self, units, R, C):
		array = [[0] * i for i in range(1, R + 2)]
		array[0][0] = units
		for row in range(1, R + 1):
			for glass in range(1, len(array[row - 1]) + 1):
				extra_water = max(0, array[row - 1][glass - 1] - 1)
				array[row - 1][glass - 1] -= extra_water
				array[row][glass - 1] += extra_water / 2
				array[row][glass] += extra_water / 2
		return round(array[R - 1][C - 1], 6)