The Balance

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem A

概要
a グラムと b グラムの２種類の重りと天秤を使い、d グラムを計るとき、以下の条件を満たすように
x (a グラムの重りの数)と y (b グラムの重りの数)を求めよ。

1. a グラムの重りを x 個、b グラムの重りを y 個使って、d グラムを計ることができる
2. 1 の条件を満たす (x, y) が複数ある場合は、(x + y) が最小のものとする
3. 1, 2 の条件を満たす (x, y) が複数ある場合は、(a*x + b*y) が最小のものとする

解法

天秤の状態を式で表すと、(a グラムの重りを a と表現します)

a*x = b*y + d （左に x 個の a、右に y 個の b と d）
a*x + d = b*y （左の x 個の a と d、右に y 個の b）
a*x + b*y = d （左り x 個の a と y 個の b、右に d）

の３つの状態が考えられます。これらを変形すると

y = (a*x - d)/b, ((a*x - d) が b で割りきれるとき)
y = (a*x + d)/b, ((a*x + d) が b で割りきれるとき)
y = (d - a*x)/b, ((d - a*x) が b で割りきれるとき)

x を 0 から b+d までについて、y を求め
(x + y) または (a*x + b*y) の最小値を更新していきます。

もちろん効率化の余地はありますし、整数論的に解けるのかもしれません。
ICPCで Accept されるには十分だと思います。

サンプルプログラム

001 #include<iostream>
002 #include<cmath>
003 #define LIMIT 50000
004 using namespace std;
005 int a, b , d, mx, my;
006 
007 void update( int x, int y, int &mx, int &my ){
008     if ( y < 0 ) return;
009     if ( x + y == mx + my && a*x + b*y < a*mx + b*my ){
010         mx = x; my = y;
011     } else if ( x + y < mx + my ){
012         mx = x; my = y;
013     }
014 }
015 
016 main(){
017     while( cin >> a >> b >> d, (a || b || d) ){
018         mx = my = LIMIT;
019         for ( int y, x = 0; x <= b + d; x++ ){
020             if ( (a*x - d)%b == 0 ){
021                 y = (a*x - d)/b; update( x, y, mx, my );
022             }
023             if ( (a*x + d)%b == 0 ){
024                 y = (a*x + d)/b; update( x, y, mx, my );
025             }
026             if ( (d - a*x)%b == 0 ){
027                 y = (d - a*x)/b; update( x, y, mx, my );
028             }
029         }
030         cout << mx << " " << my << endl;
031     }
032 }