Page 2 of 3

Posted: Thu Oct 19, 2006 6:10 pm
by Jan
helloneo wrote:I made an equation 3x + 4y = 1 (gcd(3, 4))
I got x = -1, y = 1
So, obviously you can say that
43 * 3 * x + 43 * 4 * y = 43
Lets consider that
x = 43*x = -43 and
y = 43*y = 43
Now the equation becomes
3*x + 4*y = 43
Now suppose you want to minimize y. You can rewrite
3*x + 4*y = 43
where x=-39, y=40
or x = -35, y = 37
...
or x = 13, y = 1
Now the rest is upto you. Make sure that both are non-negative. :D

Posted: Fri Oct 20, 2006 5:31 am
by helloneo
Thanks for the good explanation..
I'll try it.. :D

Posted: Mon Jan 01, 2007 10:49 pm
by jan_holmes
Could anyone of you tell me the output of this :

Code: Select all


1000
21 2
21 3
0

Thx... :)[/code]

Posted: Thu Jan 04, 2007 1:25 pm
by Jan
My accepted code returns...

Output:

Code: Select all

2 332
Hope it helps.

Posted: Tue Jan 30, 2007 8:37 am
by devious
I am confused on how the extended euclidean algorithm can be used to solve this problem.

It would seem you wouldn't need it, considering the values it returns are not the correct ones.

It is simple to come up with the equation 3x + 4y = 43 (from sample input) without the ext. euclid. Am I missing a key point here?

Thanks in advance

Posted: Tue May 22, 2007 1:08 pm
by aadelf
I tested all sets in this forum and I get the correct answer.
However I get WA online.

I solve it using extended euclid algorithm.

I can not think of any more test cases. Can any provide more?

What happens in case:

28
1 1
2 2

Posted: Tue May 22, 2007 5:40 pm
by Jan
The case is not valid I think. Make some random cases and check whether you get any negative answer or not. This can be the problem. And you can post your code, too.

Posted: Tue May 22, 2007 9:43 pm
by aadelf
I agree that the test case I mention shouldn't be correct. But I don't know what to think anymore.

Here is my code.

Code: Select all

#include <stdio.h>

int main()
{
	long n,c1,c2,n1,n2,swap,T;
	long X,Y,preX,preY,a,b,d,temp,gcd,k,m,da,db;
	double tc1,tc2;

	scanf("%d",&n);
	T=1;

	while (n!=0) {
		scanf("%d %d",&c1,&n1);
		scanf("%d %d",&c2,&n2);


		preX=1;
    	X=0;
		preY=0;
		Y=1;
	    a=n1;
		b=n2;
    	while (b!=0){
        	temp = b;
        	d = (long)a/b;
        	b = a - d*b;
        	a = temp;

        	temp = X;
        	X = preX - d*X;
        	preX = temp;

        	temp = Y;
        	Y = preY - d*Y;
        	preY = temp;
		}

		gcd = a;
		a = preX;
		b = preY;

		k = n/gcd;
		da = n2/gcd;
		db = n1/gcd;


		if ((k*gcd)!=n)
    		printf("failed\n");
		else {
			a*=k;
			b*=k;

			swap=0;
			tc1=(double)c1/n1;
			tc2=(double)c2/n2;
			if ((tc2<tc1)||((tc1==tc2)&&(n1<n2))) {
				temp=a;
				a=b;
				b=temp;

				temp=da;
				da=db;
				db=temp;

				swap=1;
			}

			if (b>=0){
				m = b/db;
				b = b - m*db;
				a = a + m*da;
			}
			else {
				m = -b/db;
				if ((b + m*db)<0) m++;
				b = b + m*db;
				a = a - m*da;
			}

			if (a<0)
				printf("failed\n");
			else{
				if (swap==1)
					printf("%d %d\n",b,a);
				else
					printf("%d %d\n",a,b);
			}
		}

		T++;
		scanf("%d",&n);
	}

	return 0;
}

Posted: Wed May 23, 2007 9:50 pm
by Jan
Try the cases.

Input:

Code: Select all

2601
6 11
32 45
247558756
11479 13625
11229 8731
32661225
5286 422
5398 4247
251001
293 359
388 180
389193984
168 5448
1999 14772
133356304
1870 8365
2572 3204
0
Output:

Code: Select all

216 5
10383 12151
2953 7397
639 120
71259 66
15892 131
Hope these help.

Posted: Thu May 24, 2007 2:41 pm
by aadelf
These test cases were exactly what I need. I found my bug. Thanks a lot.

Re: 10090 - Marbles

Posted: Tue Nov 25, 2008 9:51 pm
by andmej
I'm getting Wrong Answer.
My code passes all output in the forum.

Please help me find the bug:

Code: Select all

using namespace std;
#include <cstdio>
#include <cassert>
#include <algorithm>

long long get_gcd(long long a, long long b, long long &x, long long &y){
  if (b > a) return get_gcd(b, a, y, x);
  if (b == 0){
    x = 1, y = 0;
    return a;
  }
  long long g, sub_x, sub_y;
  g = get_gcd(b, a%b, sub_x, sub_y);
  x = sub_y, y = sub_x - sub_y*(a/b);
  return g;
}

int main(){
  long long n, n1, n2, c1, c2;
  while (scanf("%lld", &n)==1 && n){
    scanf("%lld %lld %lld %lld", &c1, &n1, &c2, &n2);

    long long a, b, gcd;
    gcd = get_gcd(n1, n2, a, b);

    if (n % gcd != 0){
      printf("failed\n");
    }else{
      a *= (n/gcd), b *= (n/gcd);
      assert(a*n1 + b*n2 == n);


      long long lcm = n1*n2 / gcd;
      long long inc_a = lcm/n1, inc_b = lcm/n2;

      if (a < 0){
        int times = -a/inc_a;
        if (-a % inc_a) ++times;
        a += times*inc_a, b -= times*inc_b;
      }

      if (b < 0){
        int times = -b/inc_b;
        if (-b % inc_b) ++times;
        b += times*inc_b, a -= times*inc_a;
      }

      if (a < 0 || b < 0) printf("failed\n");
      else{

        pair<long long, long long> ans;
        long long best = LLONG_MAX;

        if (a*c1 + b*c2 < best){
          best = a*c1 + b*c2;
          ans = make_pair(a, b);
        }

        if (a > b){
          int times = a/inc_a;
          a -= times*inc_a, b += times*inc_b;
          if (a*c1 + b*c2 < best){
            best = a*c1 + b*c2;
            ans = make_pair(a, b);
          }

        }else{
          int times = b/inc_b;
          a += times*inc_a, b -= times*inc_b;
          if (a*c1 + b*c2 < best){
            best = a*c1 + b*c2;
            ans = make_pair(a, b);
          }
        }
        printf("%lld %lld\n", ans.first, ans.second);
      }

    }
  }
  return 0;
}

Re: 10090 - Marbles

Posted: Tue Dec 09, 2008 11:14 pm
by fR0D
can sumbdy plz elaborate on how to minimise after getting x nd y for ax + by = GCD?

Re: 10090 - Marbles

Posted: Wed Dec 10, 2008 3:18 pm
by mf
In general, a solution to the linear diophantine equation ax + by = c has the form:
x = x0 + b/d t,
y = y0 - a/d t,
where (x0, y0) is any particular solution (which can be found by extended gcd), d = gcd(a, b), and t is an integer parameter.

Let's investigate for which values of t the solution is feasible for our problem (x and y are non-negative):
x0 + b/d t >= 0, y0 - a/d t >= 0, a >= 0, b >= 0, =>
-x0*d/b <= t <= y0*d/a.
And since t must be an integer, we futher have: ceil(-x0*d/b) <= t <= floor(y0*d/a).
So, all the feasible values of t form an interval of consecutive integer values.

Next, let's look at the cost function: c1 x + c2 y = (c1 x0 + c2 y0) + (c1 b/d - c2 a/d) t = (some const) + (another const) * t, i.e. it's linear in t, which means that its minimum and maximums can occur only at the boundary of feasible region.

So, just check two points t=ceil(-x0*d/b), and t=floor(y0*d/a), and choose whichever one is cheaper.

fR0D wrote:can sumbdy plz ...
Oh, for god's sake, use proper English and a spellchecker!

I won't reply to any more posts written in that style.

Re: 10090 - Marbles

Posted: Wed Dec 10, 2008 5:04 pm
by fR0D
thanks mf and i will make sure to write in proper english.
can u explain with an example.

Re: 10090 - Marbles

Posted: Fri Dec 12, 2008 9:14 am
by fR0D
My program gives correct output for all test cases here still WA.

Code: Select all

Got AC
anyone please point out my mistake.