AOJ 1248 The Balance

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。

２つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか？

重りはより少なく、軽いものを選ぶ。

解法

aの数、xがでれば、yは一つに定まる。xに関するループを回して答えを更新していく。

コード

int a, b, d;

bool cmp(int ax, int ay, int bx, int by){
  if(ax+ay != bx+by) return ax+ay < bx+by;
  return a*ax+b*ay < a*bx+b*by;
}

int main(){
  while(scanf("%d%d%d", &a, &b, &d) && a+b+d){
    int resx = (INF)/2, resy = (INF)/2, r, l, y;
    rep(x, 50000){
      r = a*x + d;
      if(!(r%b)){
    y = r/b;
    if(cmp(x,y,resx,resy)) resx = x, resy = y;
      }
      l = a*x - d;
      if(l >= 0 && !(l%b)){
    y = l/b;
    if(cmp(x,y,resx,resy)) resx = x, resy = y;
      }
      l = d - a*x;
      if(l >= 0 && !(l%b)){
    y = l/b;
    if(cmp(x,y,resx,resy)) resx = x, resy = y;
      }
    }

    printf("%d %d\n", resx, resy);
  }
  return 0;
}