Hydrate [AtCoder Beginner Contest 207 B]

https://atcoder.jp/contests/abc207/tasks/abc207_b

解説

https://atcoder.jp/contests/abc207/submissions/23803329

愚直にシミュレーションをしていって、目標が達成されれば即座に回数を答えれば答えになる。
ただ、目標が達成可能でない場合は無限に操作が行われてしまうので適当な所で打ち切って-1を出力する。

解法を聞くとそれほど難しくないのだが、これで本当にいいのか？という疑問が残る。
正直、雰囲気で自分は解いたところがあるが、回数をcntと置くと、数式で整理ができて、これでよさそうという結論になる。

数式

操作回数がcntとすると、

水色のボールは A + B * cnt
赤色のボールは C * cnt

となっていることになる。水色が赤色のD倍以下ということは、

A + B * cnt ≦ C * cnt
A ≦ C * cnt - B * cnt
A ≦ (C - B) * cnt

という感じになる。左辺は正なので、C - Bが負になれば条件は満たされない。
正として考えると、

A / (C - B) ≦ cnt

となるので、条件を満たす最小のcntはAが上限になることが分かる。
つまり、答えがある場合は、10⁵回くらいやれば達成できるということが分かる。

シミュレーション

なので10⁵回を上限に（自分は心配症なので念のため計算量が余裕で間に合う10⁶で本番はやったけれど）シミュレーションすればいい。

int A, B, C, D;
//---------------------------------------------------------------------------------------------------
int solve() {
    ll mizu = A;
    ll aka = 0;
    rep(cnt, 1, 1010101) {
        mizu += B;
        aka += C;

        if (mizu <= aka * D) return cnt;
    }
    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C >> D;
    cout << solve() << endl;
}