実は、高橋くんの目標が達成可能な場合必要な操作回数の最小値は \(A\) 以下になります。その理由を説明します。

まずはじめに、問題文中の操作や高橋くんの目標を数式で表してみましょう。高橋くんが \(x\) 回目の操作を行ったあと、箱の中のボールの個数はそれぞれ以下の通りになっています。

• 水色のボールの個数 \(\cdots\) \(A+Bx\)
• 赤色のボールの個数 \(\cdots\) \(Cx\)

また、高橋くんの目標が達成されるためには、以下が成り立っている必要があります。

• (水色のボールの個数) \(\leq D \times\)(赤色のボールの個数)

よってこの問題は以下のように表すことができます。

• \(A+Bx \leq D \times Cx\) を満たすような非負整数 \(x\) は存在するか。存在するなら、そのような \(x\) の最小値を求めよ。

\(A+Bx \leq D \times Cx\) を式変形してみましょう。

\[ A+Bx \leq D \times Cx \\ \Leftrightarrow A \leq (CDx-Bx) \\ \Leftrightarrow A \leq (CD-B)x \]

明らかに、\(CD-B\) が非正であるなら高橋くんの目標は達成されません。そうでない場合、\(x\) は \(\frac{A}{CD-B}\) の切り上げとなります。\(CD-B\) は正整数ですから、\(x\) の値は \(A\) 以下となります。

故に必要な操作回数の最小値が \(A\) 以下になることが示されました。このように、答えの上限を見積もることは非常に重要です。

実装の際は以下のように \(Θ(A)\) 回のループを回して判定すればよいです。オーバーフローには注意しましょう。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long A,B,C,D; cin >> A >> B >> C >> D;
    long long blue = A, red = 0;
    for(int i = 1; i <= A; i++){
        blue += B;
        red += C;
        if(blue <= D*red){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

なお、次のように \(O(1)\) 回の計算で答えを求めることも可能です。

実装例 (Python)

A,B,C,D = map(int,input().split())
ans = -1
diff = C*D-B
if 0 < diff:
    ans = (A+diff-1)//diff
print(ans)