Page 2 of 3
Posted: 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. Posted: Fri Oct 20, 2006 5:31 am
Thanks for the good explanation..
I'll try it.. Posted: 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]

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

Output:

Code: Select all

``2 332``
Hope it helps.

Posted: 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?

Posted: 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

Posted: 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.

Posted: 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;
}``````

Posted: 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.

Posted: Thu May 24, 2007 2:41 pm
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
My code passes all output in the forum.

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
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
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!

### Re: 10090 - Marbles

Posted: 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.

### Re: 10090 - Marbles

Posted: 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.