2021年 6月 29日旅は道連れ世は情け，化粧濃くして恋せよ乙女

まえがき

解いた問題

ABC207 B-Hydrate

[数学]

問題概要

水色のボールが最初A個，赤色のボールが0個ある．一回の操作で水色のボールをB個，赤色のボールがC個増える水色のボールが，赤色のボールのD倍以下になるためには，最小で何回操作すればいい？

この問題面白いですね。
ひとまず，x回操作をした時の，ボールの個数は,
水色: A + Bx 個, 赤色: Cx個(ケンタッキーフライド・チキン)
よってこの問題は，ケンタッキフライドチキンの定理を用いて解くことが出来ます．

まあ，とりあえず，目的は Cx * D >= A + Bxにすることです.求めるのは，これを満たすxの最小値．これを式変形すると， (CD-B)x >= A さらに変形すると， 1. (CD-B)が1以上の時 x >= A / (CD-B)
2. CD - B が0のとき 0除算ダメだから解無し？ 3. CD - B が負の時 x <= A / (CD-B) これに関してはなんだ？CD-Bが負ってことは右辺が負になるから，x（最小の操作回数)が負になるってことで，そんな操作は認められていないので解無し．

こんな感じでしょうか
ごり押しコード

int main()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if(c*d - b <= 0){
        cout << -1 << endl;
        return 0;
    }   
    ll l = (d*c - b);
    ll k = (a + l - 1) / l;
    if(k < 0){
        cout << -1 << endl;
    }else {
        cout << k << endl;
    }
}

で，何が面白いかって，解説を読んだ後なんだけど...
先ほどの

(CD-B)が1以上の時 x >= A / (CD-B)

これ．Aを正の値で割ってるから，右辺はA以下にしかならない.分かりやすく言うと，（CDーB）が1の時が右辺が最大で，Aになります．
右辺が最大でもＡってことは，次のような式が作れます（作れるのかな？）
x >= A >= A /(CD-B)
式の意味が何だったかというと，上の式を満たすxは，「水色のボールの数が赤色のボールの数のＤ倍以下になる」的な感じです．
だから，A回操作すれば，水色のボールの数が赤色のボールの数のＤ倍以下になることが保証される．
つまりは，操作回数をＡ回までシミュレーションしてやればいいんだ．
操作回数xを0からA回までroopで回して，条件を満たしたらその時のxを出すってことですね．