Three buckets pour milk in a fixed cycle: bucket 1 into bucket 2, bucket 2 into bucket 3, and bucket 3 back into bucket 1. This continues for exactly 100 operations. The problem does not require a closed-form formula or a clever cycle shortcut. It tests whether we can implement one state update precisely and repeat it in the correct order.

Mixing Milk is an excellent introduction to direct simulation. We store the current amount in each bucket, calculate the maximum legal transfer for one pour, and update the source and destination together.

Where This Fits in the USACO / CP DSA Map

• Level: USACO Bronze, Difficulty Band L1
• Pattern: Direct Simulation, Cyclic Updates, State Invariant
• Prerequisite: arrays/lists, for loops, min, modulo %, assignment and subtraction
• What this teaches: Translate a process into an exact repeatable state update and use invariants to verify the simulation.
• Where it appears again: process simulation, circular indexing, state machines, event-by-event updates

What to Study Next

• Related CP Weekly problems: CCC 2026 J4 Snail Path for step-by-step simulation, CCC 2017 S1 Sum Game for running totals, and USACO 2019 January Bronze Shell Game for testing multiple starting states (planned).
• Related Python / C++ foundations: lists/arrays, for loops, min, modulo-based circular indices, and coordinated state updates.
• Related DSA note: DSA-004 Dry Runs: checking simulation order with a state table (planned).

What the Problem Is Asking

Farmer John has three buckets, possibly with different capacities. The input gives each bucket's capacity and current amount of milk.

The pouring order is fixed:

bucket 1 -> bucket 2
bucket 2 -> bucket 3
bucket 3 -> bucket 1
repeat

During every operation, he pours as much as possible until the source bucket is empty or the destination bucket is full. After exactly 100 pours, we output the final amount in each bucket on its own line.

The official bounds are 1 <= milk <= capacity <= 10^9. The values can be large, but we should not move the milk one unit at a time. One arithmetic update simulates an entire pour.

Where Beginners Often Get Stuck

The first mistake is confusing the destination's capacity with its remaining free space. The usable space is:

free_space = capacity[target] - milk[target]

The second mistake is considering only the source amount. A transfer is limited by both the milk available at the source and the space available at the destination.

The third mistake is updating too early. We must calculate the transfer amount before changing either bucket. Otherwise, using the already-reduced source amount can produce an incorrect destination update.

Finally, the simulation must perform 100 operations, not 99. A loop over turns 0 through 99 performs exactly 100 pours.

Core Algorithm Idea

For one pour from source to target:

source_milk = milk[source]
target_space = capacity[target] - milk[target]
transfer = min(source_milk, target_space)

Then update both parts of the state:

milk[source] -= transfer
milk[target] += transfer

If the source contains less milk than the destination can accept, the source empties first. If the destination has less free space, the destination fills first. The smaller quantity is exactly the largest legal transfer.

State and Cyclic Order

We store two arrays of length three:

capacity[i] = fixed capacity of bucket i
milk[i] = current amount in bucket i

For a zero-based turn number:

source = turn % 3
target = (source + 1) % 3

The remainder cycles through 0, 1, 2, and the second modulo wraps the destination from index 2 back to index 0. Turn 99 is the 100th operation; it pours from index 0 to index 1, matching the statement.

Dry Run with the Official Sample

The official sample begins with milk amounts [3, 4, 5]:

A state table makes it easy to verify the direction, transfer amount, capacity limit, and operation count.

The Conservation Invariant

Every operation subtracts transfer from one bucket and adds the same amount to another. Therefore, the total milk never changes.

The sample starts with 3 + 4 + 5 = 12, so every later state must also sum to 12. Each amount must also remain between zero and its bucket's capacity. These invariants do not compute the answer directly, but they are powerful debugging checks.

Python Solution

capacity = [0] * 3
milk = [0] * 3

for i in range(3):
    capacity[i], milk[i] = map(int, input().split())

for turn in range(100):
    source = turn % 3
    target = (source + 1) % 3

    free_space = capacity[target] - milk[target]
    transfer = min(milk[source], free_space)

    milk[source] -= transfer
    milk[target] += transfer

for amount in milk:
    print(amount)

This version uses standard input and output, which is convenient for modern judges and local testing. The historical USACO statement uses mixmilk.in and mixmilk.out; only the input/output adapter changes if that file interface is required.

C++ Solution

#include <algorithm>
#include <array>
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    array<long long, 3> capacity{};
    array<long long, 3> milk{};

    for (int i = 0; i < 3; i++) {
        cin >> capacity[i] >> milk[i];
    }

    for (int turn = 0; turn < 100; turn++) {
        int source = turn % 3;
        int target = (source + 1) % 3;

        long long freeSpace = capacity[target] - milk[target];
        long long transfer = min(milk[source], freeSpace);

        milk[source] -= transfer;
        milk[target] += transfer;
    }

    for (long long amount : milk) {
        cout << amount << '\n';
    }

    return 0;
}

The C++ solution uses long long, which also makes a debugging sum of all three buckets safe when the total can be close to 3 x 10^9.

Why the Algorithm Is Correct

During each turn, transfer does not exceed the milk in the source, so the source cannot become negative. It also does not exceed the free space in the destination, so the destination cannot exceed its capacity.

If transfer equals the source amount, the source becomes empty. If it equals the destination's free space, the destination becomes full. Since it is the minimum of these two limits, at least one stopping condition is reached, and the operation transfers the maximum legal amount required by the statement.

The loop performs exactly 100 correct operations in the required cyclic order. Therefore, the three stored amounts after the loop are exactly the required final state.

Complexity Analysis

For a general number of pours P:

Time: O(P)
Space: O(1)

Because this problem fixes P = 100, both the running time and extra space are constant with respect to the input values. Large capacities do not increase the number of operations.

Common Mistakes

1. Using the destination capacity instead of capacity[target] - milk[target].
2. Moving milk one unit at a time and making the running time depend on the capacity.
3. Changing the source before calculating the complete transfer amount.
4. Forgetting to wrap from bucket 3 back to bucket 1.
5. Performing 99 or 101 pours instead of exactly 100.
6. Trying to exploit a sample cycle without proving it, when 100 direct updates are simpler.
7. Printing the three results on one line instead of three lines.

Review Questions

1. Why is the transfer the minimum of the source amount and destination free space?
2. How does turn % 3 generate the cyclic pouring order?
3. Why should transfer be computed before either bucket is modified?
4. Which quantity remains invariant, and how can it reveal a bug?
5. If the number of pours were changed from 100 to P, what would the time complexity be?