Contest Duration: - (local time) (100 minutes) Back to Home

## D - increment of coins Editorial by evima

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.