OJ Board

Posted: **Mon Mar 31, 2003 5:50 am**

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

Posted: **Mon Apr 14, 2003 11:57 am**

Still no reply ...
Can anyone help me ....

Posted: **Sun Sep 28, 2003 2:30 pm**

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

Posted: **Sun Sep 28, 2003 5:42 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.

Posted: **Wed Mar 03, 2004 11:35 am**

Can anyone post some test data?
I got sooooooo many WA.

Please......

Posted: **Wed Oct 20, 2004 4:53 pm**

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.

Posted: **Sat Feb 19, 2005 4:23 pm**

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?

Posted: **Sat Aug 05, 2006 1:55 pm**

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

Posted: **Sun Aug 27, 2006 6:48 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;
}

Posted: **Mon Aug 28, 2006 7:41 pm**

Try the following i/o set

Input:

Code: Select all

Output:

Code: Select all

Hope it works.

Posted: **Tue Aug 29, 2006 6:13 am**

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

Thanks in advance !!

Posted: **Tue Aug 29, 2006 7:33 am**

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

Output:

Code: Select all

Hope ir helps.

Posted: **Wed Oct 18, 2006 3:18 pm**

Hello..~
My brute force approach got me TLE..
Can anybody tell me what algorithm is needed..?

Code: Select all

code removed

Posted: **Thu Oct 19, 2006 1:14 am**

You can use Extended Euclid. Then some simulation.

Posted: **Thu Oct 19, 2006 10:53 am**

Jan wrote:You can use Extended Euclid. Then some simulation.

Thanks for the reply.
I've been thinking of extended-euclid but I still don't get it..

Code: Select all

43
1 3
2 4

For this test case..
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..?

OJ Board

10090 - Marbles

10090 - Marbles

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

10090 Marbles