The Balance
2007.09.23 23:26 ACM/ICPC 2004
問題 ACM/ICPC Asia Regional 2004 Ehime: Problem A
概要
a グラムと b グラムの2種類の重りと天秤を使い、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)
の3つの状態が考えられます。これらを変形すると
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 されるには十分だと思います。
サンプルプログラム
概要
a グラムと b グラムの2種類の重りと天秤を使い、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)
の3つの状態が考えられます。これらを変形すると
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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |