Official

B - Hydrate Editorial by en_translator


In fact, if the objective is achievable, then the minimum number of operations required is no more than \(A\). We will explain the reasons.

Firstly, let us represent the operations and Takahashi’s objective mathematically. After his \(x\)-th operation, the box has

  • \(A+Bx\) cyan balls and
  • \(Cx\) red balls.

Also, when his objective is achieved, the following relations should be satisfied:

  • (The number of cyan balls) \(\leq D \times\) (the number of red balls).

Therefore, the problem can be rephrased as follows:

  • Is there a non-negative integer \(x\) such that \(A+Bx \leq D \times Cx\)? If exists, find such minimum \(x\).

Now let us transform the inequality \(A+Bx \leq D \times Cx\).

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

Obviously, his object can never be achieved if \(CD-B\) is not positive. Otherwise, \(x\) is \(\frac{A}{CD-B}\), rounded up. Since \(CD-B\) is a positive integer, \(x\) can be at most \(A\).

Therefore we found that the minimum number of operations required is at most \(A\). As you can see, it is very important to estimate the upper bound of the answer.

For implementation, you may judge within an \(Θ(A)\) repetitions of loop as follows. Be careful of overflows.

Sample code (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;
}

Note that one may find the answer in an \(O(1)\) number of computations.

Sample code (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)

posted:
last update: