Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/808.html
808. Soup Servings
Level
Medium
Description
There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:
- Serve 100 ml of soup A and 0 ml of soup B
- Serve 75 ml of soup A and 25 ml of soup B
- Serve 50 ml of soup A and 50 ml of soup B
- Serve 25 ml of soup A and 75 ml of soup B
When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.
Note that we do not have the operation where all 100 ml’s of soup B are used first.
Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.
Example:
Input: N = 50
Output: 0.625
Explanation:
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For 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.
Notes:
0 <= N <= 10^9.- Answers within
10^-6of the true value will be accepted as correct.
Solution
Since the amount of each type of soup served in ml is always a multiple of 25, divide N by 25 and add the quotient by 1 if there is remainder. For example, if N is 50, then the result after dividing N by 25 is 2. If N is 55, then the result after dividing N by 25 is 3. Let unit be the result after dividing N by 25.
Use dynamic programming. Create a 2D array dp of type double with units + 1 rows and units + 1 columns, where dp[i][j] represents the probability that soup A will be empty first plus half the probability that A and B become empty at the same time, when starting with i units of soup A and j units of soup B, where one units equals 25 ml of soup. According to the definition, dp[0][0] = 0.5. For i from 1 to units, there is dp[0][i] = 1 and dp[i][0] = 0. Aince four operations are chosen with equal probability, it can be concluded that for 0 < i <= units and 0 < j <= units, dp[i][j] = (dp[i - 4][j] + dp[i - 3][j - 1] + dp[i - 2][j - 2] + dp[i - 1][j - 3) / 4, where negative indices are replaced with index 0 (for example, if i == 3, then dp[i - 4][j] is just the same as dp[0][j]). Finally, dp[units][units] is the required result.
If the input N is very large, the algorithm is quite time-consuming, so other means should be tried for large inputs. It can be seen that when N >= 12500 or units >= 500, the probability is quite close to 1, so simply return 1 if units >= 500. For small inputs, use dynamic programming mentioned above to calculate the probability.
-
class Solution { public double soupServings(int N) { int units = (int) Math.ceil(N / 25.0); if (units >= 500) return 1; double[][] dp = new double[units + 1][units + 1]; dp[0][0] = 0.5; for (int i = 1; i <= units; i++) { dp[0][i] = 1; dp[i][0] = 0; } for (int i = 1; i <= units; i++) { for (int j = 1; j <= units; j++) { int i1 = Math.max(i - 4, 0), j1 = j; int i2 = Math.max(i - 3, 0), j2 = Math.max(j - 1, 0); int i3 = Math.max(i - 2, 0), j3 = Math.max(j - 2, 0); int i4 = Math.max(i - 1, 0), j4 = Math.max(j - 3, 0); dp[i][j] = (dp[i1][j1] + dp[i2][j2] + dp[i3][j3] + dp[i4][j4]) / 4; } } return dp[units][units]; } } -
class Solution: def soupServings(self, n: int) -> float: @cache def dfs(i, j): 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) ############ class Solution: def soupServings(self, N): """ :type N: int :rtype: float """ self.memo = dict() if N > 5600: return 1.0 return self.solve(N, N) def solve(self, A, B): if (A, B) in self.memo: return self.memo[(A, B)] if A <= 0 and B > 0: return 1 if A <= 0 and B <= 0: return 0.5 if A > 0 and B <= 0: return 0 prob = 0.25 * (self.solve(A - 100, B) + self.solve(A - 75, B - 25) + self.solve(A - 50, B - 50) + self.solve(A - 25, B - 75)) self.memo[(A, B)] = prob return prob -
class Solution { public: double soupServings(int n) { double f[200][200] = {0.0}; function<double(int, int)> dfs = [&](int i, int j) -> double { if (i <= 0 && j <= 0) return 0.5; if (i <= 0) return 1; if (j <= 0) return 0; if (f[i][j] > 0) return f[i][j]; double ans = 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3)); f[i][j] = ans; return ans; }; return n > 4800 ? 1 : dfs((n + 24) / 25, (n + 24) / 25); } }; -
func soupServings(n int) float64 { if n > 4800 { return 1 } f := [200][200]float64{} var dfs func(i, j int) float64 dfs = func(i, j int) float64 { if i <= 0 && j <= 0 { return 0.5 } if i <= 0 { return 1.0 } if j <= 0 { return 0 } if f[i][j] > 0 { return f[i][j] } ans := 0.25 * (dfs(i-4, j) + dfs(i-3, j-1) + dfs(i-2, j-2) + dfs(i-1, j-3)) f[i][j] = ans return ans } return dfs((n+24)/25, (n+24)/25) } -
function soupServings(n: number): number { const f = new Array(200).fill(0).map(() => new Array(200).fill(-1)); const dfs = (i: number, j: number): number => { if (i <= 0 && j <= 0) { return 0.5; } if (i <= 0) { return 1; } if (j <= 0) { return 0; } if (f[i][j] !== -1) { return f[i][j]; } f[i][j] = 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3)); return f[i][j]; }; return n >= 4800 ? 1 : dfs(Math.ceil(n / 25), Math.ceil(n / 25)); }