読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
}