Contest Duration: - (local time) (100 minutes) Back to Home

## B - Many Oranges Editorial by en_translator

We consider the following yes-no question.

Question: is there a combination of $$N$$ oranges, each of whose weight is between $$A$$ grams and $$B$$ grams, inclusive, such that the sum of weight is exactly $$W$$ kilograms?

The answer for this problem is Yes if $$AN \leq 1000W \leq BN$$, otherwise No. (Imagine first choosing $$N$$ oranges of weight $$A$$ grams, and then exchanging with heavier oranges little by little)

Therefore, one can exhaustively search for every $$N$$ to find the answer. The weight is at most $$1000$$ kilograms, and an orange weighs at least $$1$$ gram, so the maximum possible number of oranges is $$1000000$$. Be careful of the range of searching.

Sample Code (C++)

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

int main(){
int a,b,w;
cin >> a >> b >> w;
int m=1e9,M=0;
for(int n=1;n<=1000000;n++){
if(a*n<=1000*w && 1000*w<=b*n){
m=min(m,n);
M=max(M,n);
}
}
if(M==0)cout << "UNSATISFIABLE";
else cout << m << ' ' << M;
}


Note that this problem can be solved in a total of $$O(1)$$ time with a proper calculation. Be careful of which to do: to round down or round up.

Sample Code (Python)

import math

a,b,w=map(int,input().split())
upper=int(math.floor(1000*w/a))
lower=int(math.ceil(1000*w/b))

if lower>upper:
print("UNSATISFIABLE")
else:
print(lower,upper)


posted:
last update: