[ARC139] B - Make N
[Q] https://atcoder.jp/contests/arc139/tasks/arc139_b
0. 1<A<Bにしたいので、A>Bならswapしちゃう。
1. 貪欲的に考えるととりあえず次の5パターンがすぐわかる。
(a) 全部1
(b) A>B>1でとる（Aで取り切れるだけとる）
(c) A>1 でとる（Aで取り切れるだけとる）
(d) B>A>1でとる（Bで取り切れるだけとる）
(e) B>1でとる（Bで取り切れるだけとる）
2. 残りのパターンが一番厄介。
(f) AとBをバランスよくとって、1を極力減らす。（探索）
これは、1のコストが高くて、AとBのコストがいい感じに低いとき。
3. まず、AとBの最小公倍数（LCM）でループするのがわかる。ループ部分は、1周だけ残して、1,A,Bのどれか最高効率で確定しちゃっていい。
なので、NがLCM+N%LCMにまず減らせる。
Q. LCM1周だけ残す？
N=36, A=5, B=7, 1のコストがとても高いときを考える。
LCM = 5*7 = 35
もしLCMを全部とってしまうと、
N % 35 = 1で、1を1個とってしまう。
けど、
N = 3*5 + 3*7 = 36
1をとらない取り方がありうる。これを漏らしたくないので、35を残しておく。
Q. LCMは1週で足りる？
35を7で割ると5つにわけられる
7%5 = 2
14%5 = 4
21%5 = 1
28%5 = 3
35%5 = 0
あまりは、1のコストで採用しないといけない個数。
剰余を網羅できるのがLCMなので、1週あれば足りる。4. Bの取り方を、0個、1個、... B/N個と探索する。
2パターンみた。
(a) B>A>1（Bを規定数とったあと、Aをできるだけとる）
(b) B>1 (Bを規定数とったあと、1をできるだけとる）
この6パターンの最小値がこたえ。
実装
int main() {
cincout();
ll T;
cin >> T;
ll N, A, B, X, Y, Z;
ll p;
rep(i, T) {
cin >> N >> A >> B >> X >> Y >> Z;
if (A > B) { // 1<A<Bにする
swap(A, B);
swap(Y, Z);
}
// 全部１
ll ans = N * X;
// loopを確定させる
ll g = gcd(A, B);
ll must = 0;
ll LCM = A * B / g;
ll loop = N / LCM - 1; // LCM1週だけ残して、AとBのバランス調整する
if (loop > 0) { // loop箇所は最高効率で処理
ll div = loop * LCM; // 確定させる分
must = div * X; // 全部1でとる
chmin(must, div / A * Y); // 全部Aでとる
chmin(must, div / B * Z); // 全部Bでとる
N -= div; // あまり+LCMで調整分まで減らす
}
// のこりはloop+端数
rep(b, N / B + 1) { // Bでとれる個数を探索する。
// いずれにせよroot(N)くらいまで減るはず
ll cand1 = 0; // b>1をできるだけ
ll cand2 = 0; // b>a>1をできるだけ
ll n = N - b * B; // のこり
cand1 = b * Z + n * X; // b>1
cand2 = b * Z + (n / A) * Y + (n % A) * X; // b>a>1
chmin(ans, cand1 + must);
chmin(ans, cand2 + must);
}
cout << ans << endl;
}
}