# ARC139-B Make N

1719diff
https://atcoder.jp/contests/arc139/tasks/arc139_b

## 解法

一般性を失わず$A\le B$を仮定する。

$A \times X \le Y$のとき、$+A$する操作を考慮しなくて良い。反対に$A\times X \gt Y$のとき、$+1$する操作を$A$回以上行う必要がない。

同様に$B\times X\le Z$のとき、$+B$をする操作を考慮しなくて良い。反対に$B\times X\gt Z$のとき、$+1$する操作を$B$回以上行う必要がない。

$A\times X\le Y$または$B\times X\le Z$が成り立つときは簡単な場合分けで解ける。そうでない場合を考える。この仮定により、$+1$する操作は$0$回以上$A - 1$回行うと考えて良い。

$B\ge \sqrt{N}$のとき、$+B$する操作の回数を全探索する。($i$回$+B$するとする。)

$B\ge \sqrt{N}$のとき$+B$する操作は$\sqrt{N}$回以下であることに注意する。

仮定$AX\gt Y$より、できる限りたくさん$+A$する操作をした方が嬉しい。このとき$+A$する操作は$\lfloor\frac{N - iB}{A}\rfloor$回である。ここから$+1$する操作回数も特定できて、コストも計算できる。

$B\lt \sqrt{N}$のとき、$+1$する回数が$\sqrt{N}$回に抑えられていることに注意する。$+1$する回数を全探索することにする($i$回)

このときは定式化して頑張ると、$+A$を可能な限りたくさんやるか、$+B$を可能な限りたくさんやるかのどちらかが最適になることがわかる。

#include <bits/stdc++.h>

// sorry!
#define int long long

const int SQ{40000};

std::mt19937 mt{std::random_device{}()};

long long brute(int N, int A, int B, int X, int Y, int Z) {
    auto f{[&](long long x, long long y, long long z) -> long long {
        assert(x + A * y + B * z == N);
        assert(x >= 0 and y >= 0 and z >= 0);
        return X * x + Y * y + Z * z;
    }};
    long long ans{f(N, 0, 0)};
    for (int y{} ; A * y <= N ; y++) for (int z{} ; A * y + B * z <= N ; z++) {
        int x{N - A * y - B * z};
        // std::cout << x << ' ' << y << ' ' << z << " -> " << f(x, y, z) << std::endl;
        ans = std::min(ans, f(x, y, z));
    }
    return ans;
}

long long solve(int N, int A, int B, int X, int Y, int Z) {
    auto f{[&](long long x, long long y, long long z) -> long long {
        if (x + A * y + B * z != N) {
            std::cout << N << ' ' << A << ' ' << B << std::endl;
            std::cout << x << ' ' << y << ' ' << z << std::endl;
            assert(false);
        }
        assert(x + A * y + B * z == N);
        assert(x >= 0 and y >= 0 and z >= 0);
        return X * x + Y * y + Z * z;
    }};
    if (A > B) {
        std::swap(A, B);
        std::swap(Y, Z);
    }
    if ((long long)A * X <= Y) { // +Aは使わないのが最適
        return std::min(f(N, 0, 0), f(N % B, 0, N / B));
    }
    if ((long long)B * X <= Z) {
        return std::min(f(N % A, N / A, 0), f(N, 0, 0));
    }
    if (B >= SQ) {
        long long ans{f(N, 0, 0)};
        for (int z{} ; z * B <= N ; z++) {
            int y{(N - z * B) / A};
            int x{(N - z * B) % A};
            ans = std::min(ans, f(x, y, z));
        }
        return ans;
    }
    else { // B < SQ
        int gcd{std::gcd(A, B)};
        int AA{A / gcd};
        int BB{B / gcd};
        long long ans{f(N, 0, 0)};
        std::vector<int> AB(BB);
        for (int i{}, j{} ; i < BB ; i++) {
            AB[j] = i;
            j = (j + AA) % BB;
        }
        // for (auto ab : AB) std::cout << ab << ' ';
        // std::cout << std::endl;
        for (int x{} ; x < B ; x++) {
            int tar{N - x};
            if (tar < 0) continue;
            if (tar % gcd) continue;
            // std::cout << "check " << x << " => "  << tar << std::endl;
            tar /= gcd;
            int y{AB[tar % BB]};
            if (tar - (long long)AA * y >= 0) {
                assert((tar - (long long)AA * y) % BB == 0);
                int z{(tar - AA * y) / BB};
                // std::cout << x << ' ' << y << ' ' << z << std::endl;
                ans = std::min(ans, f(x,  y, z));
            }
            int k{(tar - (long long)AA * y) / ((long long)AA * BB)};
            if (k >= 0) {
                y += BB * k;
                if (tar - (long long)AA * y >= 0) {
                    assert((tar - (long long)AA * y) % BB == 0);
                    int z{(tar - (long long)AA * y) / BB};
                    // std::cout << x << ' ' << y << ' ' << z << std::endl;
                    ans = std::min(ans, f(x, y, z));
                }
            }
            // std::cout << ans << std::endl;
        }
        return ans;
    }
}

signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int T;
    // T = 100;
    std::cin >> T;
    while (T--) {
        int N, A, B, X, Y, Z;
        // N = mt() % 100000000 + 1;
        // A = mt() % 100000000 + 1;
        // B = mt() % 100000000 + 1;
        // X = mt() % 100000000 + 1;
        // Y = mt() % 100000000 + 1;
        // Z = mt() % 100000000 + 1;
        std::cin >> N >> A >> B >> X >> Y >> Z;
        std::cout << solve(N, A, B, X, Y, Z) << '\n';

        // long long my{solve(N, A, B, X, Y, Z)};
        // long long bru{brute(N, A, B, X, Y, Z)};
        // if (my != bru) {
        //     std::cout << N << ' ' << A << ' ' << B << ' ' << X << ' ' << Y << ' ' << Z << std::endl;
        //     std::cout << my << ' ' << bru << std::endl;
        //     std::exit(0);
        // }
    }
}

[提出](https://atcoder.jp/contests/arc139/tasks/arc139_b)

## 感想

考察も実装もかなりダメだった。ダメだったなぁ。

この難しさの問題が1600diff程度になるなんてARC・AGC魔境すぎるよ〜。ついていけない。