次のような判定問題を考えます。

問題：\(1\) 個が \(A\) グラム以上 \(B\) グラム以下のみかんをちょうど \(N\) 個選んで \(W\) キログラムにすることはできるか？

この問題に対する答えは、\(AN \leq 1000W \leq BN\) が成り立つとき Yes、成り立たないとき No です。（最初に \(A\) グラムのみかんを \(N\) 個選んで、少しずつ大きなみかんと交換することをイメージしてみましょう）

したがって \(N\) を全探索することで答えを求めることができます。重さは最大で \(1000\) キログラム、みかん \(1\) 個は最小で \(1\) グラムなので、選んだみかんの個数として考えられる最大値は \(1000000\) 個です。探索範囲に注意してください。

回答例(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;
}

なお、この問題は適切な計算により \(O(1)\) で求めることもできます。切り上げと切り捨てのどちらで計算すべきかに注意しましょう。

回答例(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)