#808

Soup Servings

specialist · 790 · lc medium +31 · verified · 59.7% accepted · 1,454 likes · top 58%

⚑ Probability / Expected Value DP

Description

Two soups, A and B, each begin with n mL. On every turn, one of four operations is selected uniformly at random (each with probability 0.25):

 - serve 100 mL from A and 0 mL from B

 - serve 75 mL from A and 25 mL from B

 - serve 50 mL from A and 50 mL from B

 - serve 25 mL from A and 75 mL from B

Notes:

 - There is no operation that serves 0 mL from A and 100 mL from B.

 - Both servings happen simultaneously each turn.

 - If an operation calls for more soup than remains in a pot, pour everything that is left.

The process ends when either soup is depleted.

Return the probability that A is exhausted first, plus half the probability that both are exhausted simultaneously. Answers within 10-5 of the true answer are accepted.

Example 1:

Input: n = 50
Output: 0.62500
Explanation:
If we perform either of the first two serving operations, soup A will become empty first.
If we perform the third operation, A and B will become empty at the same time.
If we perform the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Example 2:

Input: n = 100
Output: 0.71875
Explanation:
If we perform the first serving operation, soup A will become empty first.
If we perform the second serving operations, A will become empty on performing operation [1, 2, 3], and both A and B become empty on performing operation 4.
If we perform the third operation, A will become empty on performing operation [1, 2], and both A and B become empty on performing operation 3.
If we perform the fourth operation, A will become empty on performing operation 1, and both A and B become empty on performing operation 2.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.71875.

Code

1
2
3