274. Soup Kitchen Odds
A soup kitchen starts with n ml of soup A and n ml of soup B. Every turn it picks one of four serving plans uniformly at random (probability 1/4 each) and serves it: (A, B) = (100, 0), (75, 25), (50, 50) or (25, 75) ml. If a soup does not have enough left, it serves whatever remains of it. The process ends when at least one soup is empty.
Return, as a double, the probability that A runs out first, plus half the probability that A and B run out in the very same turn. For large n the answer is within 1e-5 of 1, and answers within 1e-5 of the true value are accepted, so a cutoff for big inputs is allowed. Work in 25 ml units with a memoised or tabulated DP; time O(min(n, 6000)^2 / 625), space the same.
Example 1
- Input:
- n = 130
- Output:
- 0.7578125
- Explanation:
130 ml is 6 units of 25 ml; the memoised recursion over (A, B) gives about 0.758.
Example 2
- Input:
- n = 725
- Output:
- 0.9549337066709995
- Explanation:
With 725 ml each, A tends to drain faster on average, so the answer is about 0.955.
Example 3
- Input:
- n = 2400
- Output:
- 0.9990691128897385
- Explanation:
At 2400 ml each the probability is already about 0.9991 because A is served more on average.
Constraints
1 ≤ n ≤ 109
Absolute error up to 1e-5 is accepted.
Every serving amount is a multiple of 25 ml.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-5: |answer - expected| <= 1.0E-5 x max(1, |expected|).
- Tolerance
0.00001
Expected complexity
- Time
- O(1) (bounded table)
- Space
- O(1) (bounded table)