This problem is a kind of so-called probability DP.

Let \(f(X, Y, Z)\) be the answer for \(X\) gold coins, \(Y\) silver coins, and \(Z\) bronze coins. If either \(X\), \(Y\) or \(Z\) is \(100\), then \(f(X, Y, Z) = 0\). Otherwise, considering which kind of coin was chosen, we obtain

\(f(X, Y, Z) = \frac{X}{X+Y+Z} ( f(X+1, Y, Z) + 1 ) + \frac{Y}{X+Y+Z} ( f(X, Y+1, Z) + 1) + \frac{Z}{X+Y+Z} ( f(X, Y, Z+1) + 1 ).\)

(The probability of choosing a gold coin × the expected value after a gold coin is chosen + that of silver…)

If you execute DP with the equation above, you will obtain the answer. The implementation can be done easily with memorized recursion.

Sample Code ©