# LeetCode 808: Soup Servings

## Problem Restatement

We have two soups, `A` and `B`. Both start with `n` milliliters.

On each turn, one of four operations is chosen with equal probability `0.25`:

| Operation | Soup A served | Soup B served |
|---|---:|---:|
| 1 | 100 ml | 0 ml |
| 2 | 75 ml | 25 ml |
| 3 | 50 ml | 50 ml |
| 4 | 25 ml | 75 ml |

If an operation asks for more soup than remains, we serve all that remains.

The process stops immediately after a turn where at least one soup becomes empty.

Return:

```python
P(A empties first) + 0.5 * P(A and B empty at the same time)
```

Answers within `10^-5` of the actual answer are accepted.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n`, the starting amount of each soup |
| Output | A probability as a floating-point number |
| Stop condition | Stop after a turn where `A` or `B` becomes empty |
| Tie rule | If both empty together, count half of that probability |
| Accepted error | `10^-5` |

## Examples

Example 1:

```python
n = 50
```

Each soup starts with `50` ml.

The four possible first operations give:

| Operation | Result |
|---|---|
| Serve `100, 0` | A becomes empty first |
| Serve `75, 25` | A becomes empty first |
| Serve `50, 50` | A and B become empty together |
| Serve `25, 75` | B becomes empty first |

So the probability is:

```python
0.25 * (1 + 1 + 0.5 + 0) = 0.625
```

The answer is:

```python
0.625
```

Example 2:

```python
n = 100
```

The answer is:

```python
0.71875
```

## First Thought: Brute Force

A direct recursive solution can simulate all possible serving sequences.

From each state `(a, b)`, where `a` and `b` are the remaining soup amounts, we try all four operations.

The probability from that state is the average of the probabilities from the four next states.

This gives the right recurrence, but without memoization it repeats the same states many times.

## Key Insight

All serving amounts are multiples of `25`.

So instead of working in milliliters, we can work in units of `25` ml.

The operations become:

| Operation | Soup A units | Soup B units |
|---|---:|---:|
| 1 | 4 | 0 |
| 2 | 3 | 1 |
| 3 | 2 | 2 |
| 4 | 1 | 3 |

If `n` is not a multiple of `25`, we round up:

```python
units = (n + 24) // 25
```

This is safe because serving more than the remaining amount simply empties the soup.

Now define:

```python
dp(a, b)
```

as the probability that we want, starting with `a` units of soup A and `b` units of soup B.

## Algorithm

Use memoized recursion.

Base cases:

| Condition | Return value | Reason |
|---|---:|---|
| `a <= 0 and b <= 0` | `0.5` | Both soups empty together |
| `a <= 0` | `1.0` | A empties first |
| `b <= 0` | `0.0` | B empties first |

Recursive case:

```python
dp(a, b) = 0.25 * (
    dp(a - 4, b) +
    dp(a - 3, b - 1) +
    dp(a - 2, b - 2) +
    dp(a - 1, b - 3)
)
```

There is also an important optimization.

For large `n`, the probability approaches `1.0`, because soup A is served more on average than soup B. LeetCode accepts answers within `10^-5`, so we can return `1.0` once `n` is large enough. A common accepted cutoff is `n >= 4800`.

## Correctness

The function `dp(a, b)` represents the exact probability required by the problem from a state with `a` units of soup A and `b` units of soup B remaining.

If both values are non-positive, both soups became empty on the same turn, so the contribution is `0.5`.

If only `a` is non-positive, soup A became empty first, so the contribution is `1.0`.

If only `b` is non-positive, soup B became empty first, so the contribution is `0.0`.

For any state where both soups remain, the next operation is chosen uniformly from the four serving operations. Therefore, the probability from the current state is the average of the probabilities from the four possible next states.

The recursion exactly follows this transition rule, and memoization only reuses already computed state values without changing them. Therefore, `dp(units, units)` returns the required probability.

The early return for large `n` is valid for the accepted-error setting because the probability converges to `1.0`, and the cutoff is chosen so the error is within the required tolerance.

## Complexity

Let:

```python
u = ceil(n / 25)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(u^2)` | There are at most `u * u` states |
| Space | `O(u^2)` | Memoization stores state results |

With the large-`n` cutoff, the number of computed states is bounded by a constant in accepted submissions.

## Implementation

```python
from functools import cache

class Solution:
    def soupServings(self, n: int) -> float:
        if n >= 4800:
            return 1.0

        units = (n + 24) // 25

        @cache
        def dp(a: int, b: int) -> float:
            if a <= 0 and b <= 0:
                return 0.5

            if a <= 0:
                return 1.0

            if b <= 0:
                return 0.0

            return 0.25 * (
                dp(a - 4, b)
                + dp(a - 3, b - 1)
                + dp(a - 2, b - 2)
                + dp(a - 1, b - 3)
            )

        return dp(units, units)
```

## Code Explanation

The large input cutoff avoids unnecessary computation:

```python
if n >= 4800:
    return 1.0
```

Then we convert milliliters into `25` ml units:

```python
units = (n + 24) // 25
```

The `+ 24` implements ceiling division.

The memoized function stores results for repeated states:

```python
@cache
def dp(a: int, b: int) -> float:
```

The base cases encode the scoring rule:

```python
if a <= 0 and b <= 0:
    return 0.5

if a <= 0:
    return 1.0

if b <= 0:
    return 0.0
```

The recursive case averages the four equally likely operations:

```python
return 0.25 * (
    dp(a - 4, b)
    + dp(a - 3, b - 1)
    + dp(a - 2, b - 2)
    + dp(a - 1, b - 3)
)
```

Finally, we start from equal soup amounts:

```python
return dp(units, units)
```

## Testing

```python
def close(a, b, eps=1e-5):
    return abs(a - b) <= eps

def run_tests():
    s = Solution()

    assert close(s.soupServings(50), 0.625)
    assert close(s.soupServings(100), 0.71875)
    assert close(s.soupServings(1), 0.625)
    assert close(s.soupServings(25), 0.625)
    assert close(s.soupServings(4800), 1.0)

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `n = 50` | Official small example |
| `n = 100` | Official second example |
| `n = 1` | Rounds up to one 25 ml unit |
| `n = 25` | Same one-unit behavior |
| `n = 4800` | Checks large-input cutoff |