USACO 2026 Second Contest Bronze Division - Purchasing Milk#

Problem link: here

Problem Solution#

Deal $i$ sells $2^{i-1}$ buckets for $a_i$ moonies (the $a_i$ are strictly increasing), and any deal may be taken any number of times. For each query $x \le 10^9$ we must buy $\emph{at least} \ x$ buckets as cheaply as possible.

Key observations#

Only 31 deals matter: Since $x < 2^{30}$, one copy of any deal $i > 31$ already covers $x$; adding other deals beside it only raises the cost, and the purchase still costs at least $a_i \ge a_{31}$. So it is dominated by the candidate buy one copy of deal $31$, which our sweep considers anyway. Put $n = \min(N, 31)$ (larger $a_i$ are read but ignored).

Cheaper bundles: Two copies of deal $i-1$ deliver exactly $2^{i-1}$ buckets, so define $\mathrm{cost}[i] = \min(a_i,\, 2\,\mathrm{cost}[i-1])$ with $\mathrm{cost}[1]=a_1$. Then $\mathrm{cost}[i] \le 2\,\mathrm{cost}[i-1]$: the price $\emph{per bucket}$ never increases with $i$. Replacing a deal by an equivalent, possibly cheaper bundle of smaller deals never hurts, so we may price everything with $\mathrm{cost}$.

Few candidate totals: Let $F(t)$ be the minimum cost of buying exactly $t$ buckets. Since two copies of deal $i$ cost at least one deal $i+1$, repeatedly merging pairs never raises the cost, so every purchase collapses to a $\emph{canonical}$ one: one copy of each deal $1,\dots,n-1$ at every set bit of $t$, plus $\lfloor t/2^{n-1}\rfloor$ copies of the top deal $n$. This form is determined by $t$, hence $F(t)$ is computed greedily from the top deal downward.

Now let $t \ge x$ be an optimal total and $m$ the smallest deal it uses. Deleting one copy of deal $m$ leaves $t - 2^{m-1}$ buckets at cost $F(t) - \mathrm{cost}[m] < F(t)$, so optimality forces $t - 2^{m-1} < x$. All bits of $t$ below position $m-1$ are zero, so $t$ is the unique multiple of $2^{m-1}$ in $[x,\, x + 2^{m-1})$: $$ t = \bigl\lceil x / 2^{m-1} \bigr\rceil \cdot 2^{m-1}. $$ Thus only the totals ``$x$ rounded up to a multiple of $2^{m-1}$'', for $m = 1,\dots,n$, need to be checked, plus $x$ itself when the division is exact.

Therefore, one downward sweep evaluates all candidates. At level $i$, buy $\lfloor x/2^{i-1}\rfloor$ copies of deal $i$; at that moment $\texttt{cur}$ equals the canonical cost of the high bits of $x$, so $\texttt{cur + cost[i]}$ is exactly $F$ of the total rounded up at level $i$.

If the remainder ever hits $0$, $\texttt{cur}$ is precisely $F(x)$, and the code keeps it as a candidate as well.

Normalization is $O(N)$ and each query costs $O(31)$, so the total is $O(N + 31Q)$ — only a few $10^5$ operations. Answers can approach $10^{18}$, so 64-bit integers are mandatory.

Source code#

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

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 31;

long long cost[MAX_N + 1];

void solve() {
    int n, q;
    cin >> n >> q;

    int useful_n = min(n, MAX_N);

    for (int i = 1; i <= n; i++) {
        long long value;
        cin >> value;

        if (i <= useful_n) {
            cost[i] = value;
        }
    }

    for (int i = 2; i <= useful_n; i++) {
        cost[i] = min(cost[i], 2 * cost[i - 1]);
    }

    while (q--) {
        long long x;
        cin >> x;

        long long current_cost = 0;
        long long answer = (1LL << 62);

        for (int i = useful_n; i >= 1; i--) {
            long long take = x / (1LL << (i - 1));

            current_cost += take * cost[i];
            x -= take * (1LL << (i - 1));

            if (x == 0) {
                answer = min(answer, current_cost);
            }
            else {
                answer = min(answer, current_cost + cost[i]);
            }
        }

        cout << answer << "\n";
    }
}

int main() {

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

    int t = 1;

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

    return 0;
}