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;
}
