Description
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
Solution 1: Memoization Search
In this problem, since each operation is a multiple of 25, we can consider every 25ml of soup as one unit. This reduces the data scale to \left \lceil n⁄25 \right \rceil.
We design a function dfs(i, j), which represents the probability result when there are i units of soup A and j units of soup B remaining.
When i ≤ 0 and j ≤ 0, it means both soups are finished, and we should return 0.5. When i ≤ 0, it means soup A is finished first, and we should return 1. When j ≤ 0, it means soup B is finished first, and we should return 0.
Next, for each operation, we have four choices:
- Take 4 units from soup A and 0 units from soup B;
- Take 3 units from soup A and 1 unit from soup B;
- Take 2 units from soup A and 2 units from soup B;
- Take 1 unit from soup A and 3 units from soup B.
Each choice has a probability of 0.25, so we can derive:
$$ dfs(i, j) = 0.25 \times (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3)) $$
We use memoization to store the results of the function.
Additionally, we find that when n=4800, the result is 0.999994994426, and the required precision is 10^{-5}. As n increases, the result gets closer to 1. Therefore, when n \gt 4800, we can directly return 1.
The time complexity is O(C^2), and the space complexity is O(C^2). In this problem, C=200.
class Solution: def soupServings(self, n: int) -> float: @cache 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)(code-box)
