USACO 2026 First Contest Bronze Division - Chip Exchange#

Problem link: here

Problem Solution#

We first do all the obviously good transfers from \(b\) to \(a\). Each time we trade \(cb\) units of \(b\), we gain \(ca\) units of \(a\), so we perform b / cb full exchanges, add exchanges * ca to \(a\), and keep only b % cb left in \(b\). After that, we check if \(a\) is already at least \(fa\). If it is, the answer is \(0\), otherwise we still need need = fa - a more units on \(a\), and we now deliberately simulate the worst way to get there, because the problem is asking for a kind of “maximum extra cost” or “least optimal” behavior, which we store in \(x\).

From here we split into two cases. If \(cb \ge ca\), then making an exchange is “expensive” in terms of \(b\), so the worst strategy is to use as many full \(cb\)-sized chunks as possible before finally finishing off the remaining need on \(a\). If need % ca != 0, we can use floor(need / ca) of these full chunks; otherwise, to truly be inefficient, we stop one chunk earlier and leave a bit more to fix at the end. That’s why we do either cb * floor(need / ca) or cb * (need / ca - 1), then use need - 1 and finally add cb - b to account for how much more \(b\) we’d need to “waste” to make this strategy work.

If \(cb < ca\), then each exchange is relatively “cheap”, so the worst approach is simpler: just imagine adding all the remaining need - 1 to \(a\) in the least efficient way and again pay cb - b to represent how badly we’re using \(b\). In both branches we’re just translating that “opposite greedy” idea into arithmetic: first do all reasonable transfers, then assume every further move is chosen to be as bad (costly) as possible, and sum that up into \(x\), which we print as the final answer.

Source code#

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

void solve() {
    ll a, b, ca, cb, fa;
    cin >> a >> b >> ca >> cb >> fa;

    ll exchanges = b / cb;
    a += exchanges * ca;
    b %= cb;

    ll x = 0;
    if (a < fa) {
        ll need = fa - a;
        if (cb >= ca) {
            if (need % ca != 0) {
                x += cb * floor(need / ca);
                need -= ca * floor(need / ca);
            } 
            else {
                x += cb * (need / ca - 1);
                need -= ca * (need / ca - 1);
            }
            x += need - 1;
            x += cb - b;
        } 
        else {
            x += need - 1;
            x += cb - b;
        }
    }
    cout << x << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}