Buying fruits#614

Buying fruits (Editorial)

Let $x$ be the number of watermelons, $y$ be the number of apples, and $z$ be the number of plums.

We need:

$x + y + z = n$ x + y + z = n

$a x + b y + cz = m$ ax + by + cz = m

where all three numbers must be positive.

If we fix $x$ , then we only need to find $y$ and $z$ .

Let us assume that we use $i$ watermelons. Then for the remaining fruits:

$t n = n - i$ tn = n - i

$t m = m - i \cdot a$ tm = m - i \cdot a

So now we need to solve:

$y + z = t n$ y + z = tn

$b y + cz = t m$ by + cz = tm

We can rewrite $z$ as:

$z = t n - y$ z = tn - y

and substitute it into the second equation:

$b y + c (t n - y) = t m$ by + c(tn - y) = tm

$b y + c \cdot t n - cy = t m$ by + c \cdot tn - cy = tm

$y (b - c) = t m - t n \cdot c$ y(b - c) = tm - tn \cdot c

So:

$y = \frac{t m - t n \cdot c}{b - c}$ y = \frac{tm - tn \cdot c}{b - c}

After that:

$z = t n - y$ z = tn - y

So we can easily find the answer when $b \neq = c$ b \ne c.

If $b = c$ b = c, then apples and plums cost the same, so the equation for $y$ does not work. In this case, we only need to check whether:

$t m = t n \cdot b$ tm = tn \cdot b

If it is true, then any positive split of $t n$ into $y$ and $z$ is correct. Since we need the minimum number of apples, we take:

$y = 1$ y = 1

$z = t n - 1$ z = tn - 1

Here is a implementation:

#include "bits/stdc++.h"

using namespace std;

#define int long long

const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

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

    int T = 1;
    // cin >> T;
    while (T--) {
        int m, n, a, b, c;
        cin >> m >> n >> a >> b >> c;
        int A = INF, B = INF, C = INF;
        for (int i = 0; i <= n; i++) {
            int pa = i;
            int tn = n - i, tm = m - (i * a);
            int pb = (b == c ? 1 : abs((tm - c * tn) / (b - c)));
            int pc = tn - pb;
            if (min({pa, pb, pc}) > 0 && (pa * a + pb * b + pc * c) == m) {
                if (pa < A)
                    A = pa, B = pb, C = pc;
                else if (pa == A && pb < B)
                    pb = B, pc = C;
            }
        }

        if (A == INF)
            cout << "NO SOLUTION" << '\n';
        else cout << A << " " << B << " " << C << '\n';
    }
    return 0;
}