Let dp (X, Y, Z) be the answer when there are X gold coins, Y silver coins, and Z bronze coins. When any of X, Y, Z is 100, dp (X, Y, Z) = 0. If not, by considering the three cases of which coin was drawn,
It will be. (Probability of drawing gold coins x expected value of the number of operations when drawing gold coins + silver coins ...)
You can find the answer by performing DP according to this formula. Implementation is easy if done by memoization recursion.
Sample code
import sys
sys.setrecursionlimit(10 ** 6) #Raise the upper limit of recursion
def dfs(x, y, z): #Memoization recursion
if dp[x][y][z] >= 0: #If the value is already known, return it as it is.
ret = dp[x][y][z]
else: #If the value is not known, find the value by a recurrence formula.
ret = 0
S = x + y + z
ret += x / S * (dfs(x+1, y, z) + 1)
ret += y / S * (dfs(x, y+1, z) + 1)
ret += z / S * (dfs(x, y, z+1) + 1)
dp[x][y][z] = ret #Note
return ret
X, Y, Z = map(int, input().split())
M = 100
dp = [[[-1] * (M + 1) for _ in range(M + 1)] for _ in range(M + 1)]
#Termination condition (initialization)
for i in range(A, M + 1):
for j in range(B, M + 1):
for k in range(C, M + 1):
if i == M or j == M or k == M:
dp[i][j][k] = 0
# dp(X, Y, Z)The answer that
print(dfs(X, Y, Z))
Recommended Posts