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:
Note:
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