You begin with two types of soup, A and B, each containing n milliliters. During each turn, exactly one of the following four operations is selected uniformly at random (each with probability $0.25$), independent of all prior turns:

• 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.

The serving from both soups happens simultaneously in each turn. If an operation requires serving more than the remaining amount of a particular soup, simply serve whatever is left of that soup. The process terminates immediately after any turn in which at least one soup becomes empty.

Compute and return the probability that soup A becomes empty before soup B, plus half the probability that both soups become empty at the same time. Answers within $10^{-5}$ of the true value will be accepted.

Note: There is no operation that serves $0$ mL of soup A and $100$ mL of soup B.

Constraints:

• $0 \leq$ n $\leq 10^9$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.