Need help understand the full solution for problem #3 Purchasing Milk

Problems and Contests
#1

In the code below, x is the minimum necessary remaining milk to purchase. Because it iterates from largest deal to smallest, it never seems to have a way of updating curCost if it finds a better per-bucket-price deal at a smaller size. Can someone explain? Also, I don’t understand why you can ignore all deals greater than 2^{30} in size—I know you will never need to purchase more than one of those, but couldn’t there be a really great deal among those, like 2^{40} buckets for $1?

void solve()
{
    int N, K, Q;
    scanf("%d %d", &N, &Q);
 
    int price[N];
    scanf("%d", &price[0]);
    for (int idx = 1; idx < N; ++idx)
    {
        scanf("%d", &price[idx]);
        price[idx] = min(price[idx], 2 * price[idx-1]);
    }
 
    for (int idx = 0; idx < Q; ++idx)
    {
        int x;
        scanf("%d", &x);
 
        long long minCost = 1e18;
        long long curCost = 0;
        for (int jdx = min(30, N-1); jdx >= 0; --jdx)
        {
            int curBuckets = 1<<jdx;
            long long count = x / curBuckets;
 
            x -= count*curBuckets;
            curCost += count*price[jdx];
 
            if (x == 0)
                minCost = min(minCost, curCost);
            else
                minCost = min(minCost, curCost + price[jdx]);
        }
 
        printf("%lld\n", minCost);
    }
}
#2

This is handled by the minimum in the first for loop.

The problem statement has the constraint a_i<a_{i+1}.

#3

@Benq thank you. My confusion comes from the fact that x represents the remaining buckets and always seems to go down, so I don’t understand where it recomputes the deal for the entire original number of buckets. But don’t reply yet, I suspect I may be able to figure this out if I think about it more. I think I’m getting confused by the name curCost, as it isn’t really the cost we end up with, just the hypothetical cost at this level, or something like that.

#4

@Benq I think I might see it. I wasn’t looking at the first for loop, kind of just went into the background of my mind as the code that was reading the prices, but I see the min there now. So in summary, the algorithm first sets up the deal prices so that you only get better deals as you go up in i. So you only would take lower deals (worse deals) if you can save money compared to buying too much at the higher deal. The reason that x always goes down is that at each deal we know there is no better deal available at lower prices, so at the level we’re at we know we can grab as much as we need and possible one more deal, no need to consider if waiting for a lower level would give a better deal. Something like that.