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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Thanks for the good explanation..
I'll try it..

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
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:
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
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
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:
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
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:
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
These test cases were exactly what I need. I found my bug. Thanks a lot.

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

### Re: 10090 - Marbles

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

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

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

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

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.