10090 - Marbles

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Oct 19, 2006 6:10 pm

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
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Oct 20, 2006 5:31 am

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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jan 01, 2007 10:49 pm

Could anyone of you tell me the output of this :

Code: Select all


1000
21 2
21 3
0

Thx... :)[/code]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 04, 2007 1:25 pm

My accepted code returns...

Output:

Code: Select all

2 332
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

devious
New poster
Posts: 13
Joined: Wed Feb 22, 2006 1:26 am

Post by devious » Tue Jan 30, 2007 8:37 am

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
New poster
Posts: 5
Joined: Fri May 18, 2007 7:30 pm

Post by aadelf » Tue May 22, 2007 1:08 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue May 22, 2007 5:40 pm

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.
Ami ekhono shopno dekhi...
HomePage

aadelf
New poster
Posts: 5
Joined: Fri May 18, 2007 7:30 pm

Post by aadelf » Tue May 22, 2007 9:43 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 23, 2007 9:50 pm

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.
Ami ekhono shopno dekhi...
HomePage

aadelf
New poster
Posts: 5
Joined: Fri May 18, 2007 7:30 pm

Post by aadelf » Thu May 24, 2007 2:41 pm

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

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10090 - Marbles

Post by andmej » Tue Nov 25, 2008 9:51 pm

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;
}
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 10090 - Marbles

Post by fR0D » Tue Dec 09, 2008 11:14 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10090 - Marbles

Post by mf » Wed Dec 10, 2008 3:18 pm

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.

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 10090 - Marbles

Post by fR0D » Wed Dec 10, 2008 5:04 pm

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

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 10090 - Marbles

Post by fR0D » Fri Dec 12, 2008 9:14 am

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

Code: Select all

Got AC
anyone please point out my mistake.
Last edited by fR0D on Fri Dec 12, 2008 12:17 pm, edited 1 time in total.

Post Reply

Return to “Volume 100 (10000-10099)”