AOJ : 1248 - The Balance

問題概要

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

1つの薬、2種類のおもり(A,B)、左と右に皿がついた天秤、がある。
各おもりの個数に制限はなく、何個でも使ってよい。
おもりAの個数x・重さa、おもりBの個数y・重さbとするとき、次のようになるx、yを求めるのがこの問題。

• 次の3条件の内、どれかを満たす
  • 薬を左の皿に、おもりAをx個左の皿に、おもりBをy個右の皿に置いたとき、つり合いが取れる
  • 薬を右の皿に、おもりAをx個左の皿に、おもりBをy個右の皿に置いたとき、つり合いが取れる
  • 薬を右の皿に、おもりAをx個左の皿に、おもりBをy個左の皿に置いたとき、つり合いが取れる
• このとき、(x+y)が最小になる
• (x+y)が最小になるものが複数ある場合、(ax+by)が最小になるものを選択

アルゴリズム

おもりAの個数をループで決めてやれば、おもりBの個数も自然に決定されるので、これで解く。
このときのAの個数の上限は、考えるのが面倒だったため、適当に100000にした。

プログラム

#include <stdio.h>

#define INF 999999999

//答えを更新すべきなら更新する
void updateAns(int a,int b,int ta,int tb,int *ans_a,int *ans_b){
  if(*ans_a + *ans_b > ta + tb){
    *ans_a = ta;
    *ans_b = tb;
  }
  else if(*ans_a + *ans_b == ta + tb){
    if(a * ta + b * tb < a * (*ans_a) + b * (*ans_b)){
      *ans_a = ta;
      *ans_b = tb;
    }
  }
}

int main(void){
  int i,j;
  int a,b,d;
  int ta,tb,ans_a,ans_b;

  while(scanf("%d%d%d",&a,&b,&d) && (a||b||d)){
    ans_a = INF;
    ans_b = INF;

    for(i=0;i<=100000;i++){
      //左の皿にdを乗せる
      if((a * i + d) % b == 0){
        ta = i;
        tb = (a * i + d) / b;
        updateAns(a,b,ta,tb,&ans_a,&ans_b);
      }
      //右の皿にdを乗せる
      if(a * i >= d && (a * i - d) % b == 0){
        ta = i;
        tb = (a * i - d) / b;
        updateAns(a,b,ta,tb,&ans_a,&ans_b);
      }
      //右の皿にdを乗せて,計測用のおもりは全て左
      if(a * i <= d && (d - a * i) % b == 0){
        ta = i;
        tb = (d - a * i) / b;
        updateAns(a,b,ta,tb,&ans_a,&ans_b);
      }
    }

    printf("%d %d\n",ans_a,ans_b);
  }

  return 0;
}