> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Soup Servings Python Solution with Tests

> Tested Python solution for LeetCode 808 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 808, [Medium](/catalog/medium). Topics: [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), Probability and Statistics. [View on LeetCode](https://leetcode.com/problems/soup-servings/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 808   # by problem number
lcpy gen -s soup_servings   # by problem name
```

## Problem

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:

* pour 100 mL from type A and 0 mL from type B
* pour 75 mL from type A and 25 mL from type B
* pour 50 mL from type A and 50 mL from type B
* pour 25 mL from type A and 75 mL from type B

Note:

* There is no operation that pours 0 mL from A and 100 mL from B.
* The amounts from A and B are poured simultaneously during the turn.
* If an operation asks you to pour more than you have left of a soup, pour all that remains of that soup.

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.

### Examples

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

```
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 \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/soup_servings/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/soup_servings/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from functools import cache


class Solution:
    # Time: O(n^2) after scaling n down to units of 25 mL, capped by the
    # shortcut that treats n >= 5000 as an immediate A loss
    # Space: O(n^2) for the memo table
    def soup_servings(self, n: int) -> float:
        units = (n + 24) // 25
        if units >= 200:
            return 1.0

        @cache
        def dp(soup_a: int, soup_b: int) -> float:
            if soup_a <= 0 and soup_b <= 0:
                return 0.5
            if soup_a <= 0:
                return 1.0
            if soup_b <= 0:
                return 0.0
            return (
                dp(soup_a - 4, soup_b)
                + dp(soup_a - 3, soup_b - 1)
                + dp(soup_a - 2, soup_b - 2)
                + dp(soup_a - 1, soup_b - 3)
            ) / 4

        return dp(units, units)
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) after scaling n down to units of 25 mL, capped by the | O(n^2) for the memo table |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.