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: