10090  Marbles
Moderator: Board moderators

 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 ?
I've try to think about this, but my brain don't want cooperate.
Ahhh... My poor mathematics...
If someone have time please help ...
Regards,
RS
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 ?
I've try to think about this, but my brain don't want cooperate.
Ahhh... My poor mathematics...
If someone have time please help ...
Regards,
RS

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

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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?
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 ??
Thank in advance
I think my algorithm is right, but somehow I keep getting WA !!
Can anyone who gets ACC give me some testcases ??
Thank in advance
My WA approuch is, (please, helpme)
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?
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;
}
Try the following i/o set
Input:
Output:
Hope it works.
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
Code: Select all
37 111
67 110
8 112
38 111
68 110
69 110
70 110
Ami ekhono shopno dekhi...
HomePage
HomePage
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:
Output:
Hope ir helps.
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
Code: Select all
10 10
10 10
0 10000
10000 0
Ami ekhono shopno dekhi...
HomePage
HomePage
Hello..~
My brute force approach got me TLE..
Can anybody tell me what algorithm is needed..?
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.
Thanks for the reply.Jan wrote:You can use Extended Euclid. Then some simulation.
I've been thinking of extendedeuclid but I still don't get it..
Code: Select all
43
1 3
2 4
I made an equation 3x + 4y = 1 (gcd(3, 4))
I got x = 1, y = 1
What else I can do..?
Would you give me some more hints..?