AOJ 1248,PKU 2142 The Balance

問題概要

二つの重りの重さa,b(a≠b)と，測りたい物体の重さdが与えられる．
二つの重さの一致のみを調べることが出来る天秤を用いて重さdを測るには，二つの重りがそれぞれ何個必要か．
ただし，出来るだけ合計の個数が少なくなるようにし，さらに出来るだけ合計の重さが少なくなるようにしなければならない．

解法

2つの重りはそれぞれが別の天秤皿に載せるか，同じ天秤皿に載せるかの2パターン．

また，どちら側の天秤皿で測りたい物体を測定するかの2パターンがあるので合計3通りについて調べる．

このとき，一種類につきmax(a,b,d)より多くの個数の重りを用いることはないので計算量はO(a+b+d)となる．

実装(C++)

下手な実装
#include <iostream>
#define REP(i,x) for(int i=0;i<(int)(x);i++)
using namespace std;
int a,b,d;
int main() {
	for(;cin>>a>>b>>d;){
		if(a==0&&b==0&&d==0)break;
		int x=9999999,y=999999;
		REP(i,a+1){
			if((b*i+d)%a==0){
				int nx=(b*i+d)/a,ny=i;
				if(nx+ny<x+y){
					x=nx;y=ny;
				}else if(nx+ny==x+y){
					if(nx*a+ny*b<x*a+y*b){
						x=nx;y=ny;
					}
				}
			}
		}
		swap(a,b);
		REP(i,a+1){
			if((b*i+d)%a==0){
				int ny=(b*i+d)/a,nx=i;
				if(nx+ny<x+y){
					x=nx;y=ny;
				}else if(nx+ny==x+y){
					if(nx*a+ny*b<x*a+y*b){
						x=nx;y=ny;
					}
				}
			}
		}
		//片側に全て載せる
		swap(a,b);
		REP(i,d){
			if(d-i*a<0)break;
			if((d-i*a)%b==0){
				int nx=i,ny=(d-i*a)/b;
				if(nx+ny<x+y){
					x=nx;y=ny;
				}else if(nx+ny==x+y){
					if(nx*a+ny*b<x*a+y*b){
						x=nx;y=ny;
					}
				}
			}
			if(a==0)break;
		}
		cout << x <<" " << y << endl;
	}
	return 0;
}