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

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

10090 - Marbles

Post by Red Scorpion » Mon Mar 31, 2003 5:50 am

Haiii.. :cry: :cry:

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

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

Post by Red Scorpion » Mon Apr 14, 2003 11:57 am

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

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » 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 ??

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » 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.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Wed Mar 03, 2004 11:35 am

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

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » 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.
__nOi.m....

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

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

Post by Faisal_Bd » 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?

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

10090 Marbles

Post by Bluefin » 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 8)

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Post by rcrezende » 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;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Aug 28, 2006 7:41 pm

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:

Post by Bluefin » 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 !! :cry:

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

Thanks in advance !!
"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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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

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

Post by helloneo » 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
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Oct 19, 2006 1:14 am

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

Post by helloneo » 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..?

Post Reply

Return to “Volume 100 (10000-10099)”