10090 - Marbles

[Jan]

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.

[helloneo]

Thanks for the good explanation..
I'll try it..

[jan_holmes]

Could anyone of you tell me the output of this :

Code: Select all

1000
21 2
21 3
0

Thx... [/code]

[Jan]

My accepted code returns...

Output:

Code: Select all

2 332

Hope it helps.

[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

[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

[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.

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

[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.

[aadelf]

These test cases were exactly what I need. I found my bug. Thanks a lot.

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

[fR0D]

can sumbdy plz elaborate on how to minimise after getting x nd y for ax + by = GCD?

[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.

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.

[fR0D]

thanks mf and i will make sure to write in proper english.
can u explain with an example.

[fR0D]

My program gives correct output for all test cases here still WA.

Code: Select all

Got AC

anyone please point out my mistake.