AOJ1248 The Balance

問題リンク The Balance

• 概要

aグラムとbグラムの錘を使ってdグラムを量りたい。使う錘の個数を最小化せよ。そのような個数の組み合わせが複数ある場合は錘の総重量が最も軽いものを答えよ。a, bの錘を使ってdグラムを量れないということは起こらないことが保証されている。
a≠b
a, b <= 10000
d <= 50000

• 解法

dグラムの量り方としては
1. dグラムを乗せた方の皿にx個のa、反対にy個のbを置く
2. dグラムを乗せた方の皿にy個のb、反対にx個のaを置く
3. dグラムを乗せてないの皿にx個のaとy個のbを置く
があります。これら3パターン全てについて錘を使う最小個数を数え、その中で総重量の軽いものが答えとなります。

• ソース

import java.util.Scanner;

//The Balance
public class AOJ1248 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int a = sc.nextInt(), b = sc.nextInt(), d = sc.nextInt();
			if((a|b|d)==0)break;
			int ax = -1, ay = -1;
			int x = 0, t = d;
			while(t%b!=0){
				t+=a; x++;
			}
			int y = t/b;
			ax = x; ay = y;
			y = 0; t = d;
			while(t%a!=0){
				t+=b; y++;
			}
			x = t/a;
			if(x+y<ax+ay||x+y==ax+ay&&a*x+b*y<a*ax+b*ay){
				ax = x; ay = y;
			}
			t = 0; x = 0;
			for(;t<=d;){
				if((d-t)%b==0){
					y = (d-t)/b;
					if(x+y<ax+ay||x+y==ax+ay&&a*x+b*y<a*ax+b*ay){
						ax = x; ay = y;
					}
				}
				x++; t+=a;
			}
			System.out.println(ax+" "+ay);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1248().run();
	}
}