AOJ 1248 : The Balance
問題リンク:The Balance | Aizu Online Judge
解法:
xの値をループで決めて実際に条件を満たすもののなかで最小のものを探した
xを決めるとyの値も一意に定まる
ループの上限はdだと少ないみたいだったので適当に大きくした
コード:
int a,b,d; struct P { int x,y; P(int x=-1,int y=-1):x(x),y(y){} bool operator < (const P &p)const { if(x+y != p.x+p.y)return x+y < p.x+p.y; if(a*x+b*y != a*p.x+b*p.y)return a*x+b*y < a*p.x+b*p.y; if(x != p.x)return x < p.x; return y < p.y; } }; int main() { while(cin >> a >> b >> d,a|b|d) { int ans_x = (1<<28),ans_y = (1<<28); P p = P(ans_x,ans_y); for(int x = 0;x <= 50000;x++) { int y; if((a*x+d)%b == 0) { y = (a*x+d)/b; P pp = P(x,y); p = min(p,pp); } if(x*a-d >= 0 && (x*a-d)%b == 0) { y = (x*a-d)/b; P pp = P(x,y); p = min(p,pp); } if(d-x*a >= 0 && (d-x*a)%b == 0) { y = (d-x*a)/b; P pp = P(x,y); p = min(p,pp); } } ans_x = p.x,ans_y = p.y; cout << ans_x << " " << ans_y << endl; } return 0; }