Skip to content

826. Soup Servings

Math Dynamic Programming Probability and Statistics

Problem - Soup Servings

Medium

You have two soups, A and B, each starting with n mL. On every turn, one of the following four serving operations is chosen at random, each with probability 0.25 independent of all previous turns:

  • pour 100 mL from type A and 0 mL from type B
  • pour 75 mL from type A and 25 mL from type B
  • pour 50 mL from type A and 50 mL from type B
  • pour 25 mL from type A and 75 mL from type B

Note:

  • There is no operation that pours 0 mL from A and 100 mL from B.
  • The amounts from A and B are poured simultaneously during the turn.
  • If an operation asks you to pour more than you have left of a soup, pour all that remains of that soup.

The process stops immediately after any turn in which one of the soups is used up.

Return the probability that A is used up before B, plus half the probability that both soups are used up in the same turn. Answers within 10-5 of the actual answer will be 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.

 

Constraints:

  • 0 <= n <= 109

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from functools import lru_cache
class Solution:
    def soupServings(self, n: int) -> float:
        @lru_cache(None)
        def dfs(i: int, j: int) -> float:
            if i <= 0 and j<= 0:
                return 0.5
            if i <= 0:
                return 1
            if j <= 0:
                return 0

            return 0.25*(dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3))

        return 1 if n > 4800 else dfs((n + 24) // 25, (n + 24) // 25)

Submission Stats:

  • Runtime: 7 ms (90.80%)
  • Memory: 19.5 MB (68.26%)