## 10090 - Marbles

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 10090 - Marbles

Haiii..

I've stuck in this problem.
Input (n, n1, n2);

n = x*n1 + y*n2;
aim :to find the minimum(x,y) -> minimum cost.

But how can we find the minimum x and y?

n = x*n1 + y*n2;
n = (x+a) * n1 + (y+b) * n2,

with : a*n1 + b*n2 = 0.

Example : n = 43, n1 = 3, n2 = 4; c1 = 1, c2 = 2. (sample input in p_10090).

use the extended euclid algorithms we get :
43 = (-43) * 3 + (43) * 4.

but how to minimize -43 and 43 into :
43 = 13 * 3 + 1 * 4 ?

Ahhh... My poor mathematics...

Regards,
RS

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Can anyone help me ....

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
I've got exactly the same problem, it's driving me crazy !!
Could anyone who got AC tell us some tricky input, or other tricks to solve this damn one please ??

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
I don't think there is "tricky input" here; the only problem with my code above was that I wrote if (y % n2 != 0) m++, when n1 should replace n2 (the problems of cut & paste!) It took me several days to realize this.. Check out your code for this kind of silly mistakes.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
Can anyone post some test data?
I got sooooooo many WA.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
david,
you can check this input:
input wrote: 8
5 3
8 8
output wrote: 0 1
but your code outputs "failed" for this input.
__nOi.m....

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am

### 10090 Marbles -- what's the algorithm for minimization??

I tried to solve this problem using Extended Euclid Algorithm. But got TLE. I think I could not optimize the solution properly. Can anybody share his algorithm as to how he minimizes the cost after getting a solution by Extended Euclid Algorithm?

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

### 10090 Marbles

I have tried hard to solve problem 10090.
I think my algorithm is right, but somehow I keep getting WA !!
Can anyone who gets ACC give me some testcases ??

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am
My WA approuch is, (please, help-me)

let n, c1,c2, v1, v2 (positives integers).

The Objective is minimize (v=v1*x+v2*y)
where n = c1*x + c2*y
x,y are integers >= 0

So, my idea is

From
1) n = c1*x + c2*y

I can write:

A) n - c2*y = c1*x
B) n - c1*x = c2*y

So,

A1) c1*x = n (mod c2)
B1) c2*y = n (mod c1)

Now, we have two modular linear equations.
Can I assume that x and y are one solution from theses equations?

Code: Select all

``````#include <stdio.h>

long long int mod(long long int a, long long int n) {
return (a%n + n)%n;
}

long long int mdc(long long int a, long long int b, long long int *x, long long int *y) {
long long int xx, yy, d;
if(b==0) {
*x=1; *y=0;
return a;

}
d = mdc(b, a%b, &xx, &yy);
*x = yy;
*y = xx - a/b*yy;
return d;
}

long long int solve(long long int a, long long int b, long long int n) {
long long int d, x, y;
a = mod(a, n);
b = mod(b, n);
d = mdc(a, n, &x, &y);
if(b%d==0)
return mod( ((long long)x%(n/d)) * ((b/d)%(n/d)) , n/d );
else
return -1;
}

int main(void) {
long long int x,y,n,c1,c2,d,xmin,ymin,v1,v2,v_a,v_b,x0,y0, x_a, y_a,x_b,y_b,vmin,i;
while(1) {
scanf("%Ld", &n);
if(n==0) break;

scanf("%Ld %Ld %Ld %Ld", &v1, &c1, &v2, &c2);

d = mdc(c1,c2, &x, &y);

if(n % d)  {
printf("failed\n");
continue;
}

x0 = solve(c1, n, c2);
y0 = solve(c2, n, c1);

if(x0*v1 > y0*v2) {
xmin = x0;
ymin = (n - c1*xmin)/c2;
} else {
ymin = y0;
xmin = (n - c2*ymin)/c1;
}

printf("%Ld %Ld\n", xmin, ymin);
}

return 0;
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the following i/o set

Input:

Code: Select all

``````9990
3 3
88 89
9991
3 3
88 89
9992
3 3
88 89
9993
3 3
88 89
9994
3 3
88 89
9997
3 3
88 89
10000
3 3
88 89
0``````
Output:

Code: Select all

``````37 111
67 110
8 112
38 111
68 110
69 110
70 110``````
Hope it works.
Ami ekhono shopno dekhi...
HomePage

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:
Thanks for your test cases !!

My code gives the correct output, but still WA !!
How come ~~ I am frustrated !!

Can you give me more tricky test cases ??
Or tell me how you solve the problem ~~

"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I havent solved the problem yet. I m still working. My previous code was unable to find output for the above test cases.

To generate test cases you can use any rendom function, and for correct output you can make a brute force solution.

However here are some other test cases.

Input:

Code: Select all

``````10000
1 1
998 999
10000
998 999
1 1
10000
1000 999
1 1
10000
1 1
1000 999
0``````
Output:

Code: Select all

``````10 10
10 10
0 10000
10000 0``````
Hope ir helps.
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Hello..~
My brute force approach got me TLE..
Can anybody tell me what algorithm is needed..?

Code: Select all

``````code removed
``````
Last edited by helloneo on Fri Oct 20, 2006 5:30 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You can use Extended Euclid. Then some simulation.
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Jan wrote:You can use Extended Euclid. Then some simulation.
``````43