Soup Servings
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, each equally likely (probability 0.25):
- 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 choose one operation. If the total amount of soup is not enough for the chosen operation, we serve whatever we have.
Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time. Answers within 10^-5 of the actual answer will be accepted.
Examples
Input: 50
Output: 0.625
Input: 100
Output: 0.71875
Hints
For large n (approximately >= 4800), the probability converges to 1.0. Return 1.0 early to avoid TLE.
Scale n by dividing by 25 (operations are in multiples of 25). Use memoized recursion with states (a, b) representing remaining soup amounts.
Define P(a, b) = probability A empties first + 0.5 * probability both empty simultaneously. Use 4 operations each with probability 0.25.
Related Problems
Soup Servings
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, each equally likely (probability 0.25):