Plus Or Multiple Operation [yukicoder 915]

https://yukicoder.me/problems/no/915

解説

https://yukicoder.me/submissions/393231

よーく見ると、C進数っぽく見える。
なので、C進数っぽく考えて最小コストを作ろう。
と思ったら合わない！
最後の12 2 3は(2 + 2) * 3の3手が最短。
★2だしなぁと思って方針を探すと、Cの倍数じゃないなら、Cの倍数になるよう減らして、
Cで割るのを繰り返す。
(C-1)*2あたりがコーナーケースになりそう。
これ以下になっていれば2回か。

C = 1がコーナーケース。クッキーを作れないので-1

int A, B, C;
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> A >> B >> C;

    if (C == 1) {
        cout << -1 << endl;
        return;
    }

    ll ans = 0;
    while (0 < A) {
        if (A < C) {
            ans += B;
            break;
        }

        if (A <= 2LL * (C - 1)) {
            ans += 2LL * B;
            break;
        }

        if (A % C != 0) {
            A = A - (A % C);
            ans += B;
        }
        else {
            A /= C;
            ans += B;
        }
    }
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int Q; cin >> Q;
    rep(q, 0, Q) solve();
}