Page 3 of 3

### Re: 10090 - Marbles

Posted: Fri Dec 12, 2008 10:02 am
First, you don't need floating point arithmetic to compute ceil and floor of a rational number. If x and y are positive, then floor(x/y) = x/y, and ceil(x/y) = (x+y-1)/y.
(The '/' on right-hand sides means integer division here, of course.)

Second, as I said, all feasible values of t lie in an interval, specified by this inequality: 'ceil(-x0*d/b) <= t <= floor(y0*d/a)'. This interval can be empty, which would mean no solutions. You forgot to check that.

### Re: 10090 - Marbles

Posted: Fri Dec 12, 2008 12:16 pm
Thanks mf
Got AC finally.
But some clarification :
First of all the range is
not ceil(x0*d/b) <= t <= floor(y0*d/a)
it is ceil(-x0*d/b) <= t <= floor(y0*d/a)

### Re: 10090 - Marbles

Posted: Fri Dec 12, 2008 12:26 pm

I've edited my post to fix that, so that it won't confuse somebody else.

### Re: 10090 - Marbles

Posted: Thu May 14, 2009 5:28 am
Can anyone tell me why the answer is wrong?

input
133356304
1870 8365
2572 3204

output
3076 33591

my code:

Code: Select all

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

struct val{
long long int x;
long long int y;
};

int tam,resp;
long long int x,y;
long long int Pa, Pb;
long long int cust1,cust2,cap1,cap2,qt,d;
struct val eq1, eq2;

//http://ghaeser.sites.uol.com.br/diofanti.htm
int gdce(long long int a,long long int b){
d=tam=0;
x = y =0;
long long int f;
long long int t = 0; x = 1; y = 0;
while (b != 0){
tam++;
t = t+1; Pa[t] = a; Pb[t] = b;
f = a % b; a = b; b = f;
}
for (int i = t; i<=1; i--){
f = y;
y = (long long int)x - (long long int)floor(Pa[i]/Pb[i])*y;
x = f;
}
d = a;
}

void findValues(){
eq1.x = (long long int)x;
eq1.y = (long long int)y;
int i;
for (i = 2; i <= tam+1; i++){
eq1[i].x = (long long int)eq1[i-1].y;
eq1[i].y = (long long int)eq1[i-1].x - (Pa[tam-i+2]/Pb[tam-i+2]) * eq1[i-1].y;
}
tam = i-1;
}

int main(){
long long int t1, x1, y1, c1, t2, x2, y2, c2;
while(scanf("%d",&qt)){
if (qt==0) break;
scanf("%d",&cust1);
scanf("%d",&cap1);
scanf("%d",&cust2);
scanf("%d",&cap2);

d = gdce(cap1,cap2);
findValues();
x = (long long int)eq1[tam].x * qt;
y = (long long int)eq1[tam].y * qt;
if (qt % d ==0){
t1 = (long long int) -x/cap2;
x1 = (long long int) x + cap2/d * t1;
y1 = (long long int) y - cap1/d * t1;
c1 = (long long int) cust1*x + cust2*y;

t2 = (long long int) y/cap1;
x2 = (long long int) x + cap2/d * t2;
y2 = (long long int) y - cap1/d * t2;
c2 = (long long int) cust1*x + cust2*y;
if (x1>=0 && y1>=0 && (c1<c2 || c1==c2)){
x = x1;
y = y1;
resp = 1;
} else if (x2>=0 && y2>=0 && (c2<c1 || c1==c2)){
x = x2;
y = y2;
resp = 1;
} else {
resp = 0;
}
} else {
resp = 0;
}

if (resp){
printf("%I64d %I64d\n", x,y);
} else {
printf("failed\n");
}
}
}
``````
If you can say where is my mistake i will be thankful

### Re: 10090 - Marbles

Posted: Fri May 15, 2009 1:24 pm
up

### Re: 10090 - Marbles

Posted: Fri Jun 12, 2009 5:28 am
use %lld

### Re: 10090 - Marbles

Posted: Wed May 19, 2010 7:41 pm
Pedro wrote:Can anyone tell me why the answer is wrong?

input
133356304
1870 8365
2572 3204

output
3076 33591

If you can say where is my mistake i will be thankful
Try this:

Code: Select all

``````100
1 2
2 4
100
2 2
1 4
133356304
1870 8365
2572 3204
0``````
AC output:

Code: Select all

``````0 25
0 25
15892 131
``````

### Re: 10090 - Marbles

Posted: Thu Feb 03, 2011 2:17 pm
Try these

Input:

Code: Select all

``````1791
2000000000 13
1 21
1791
1 21
10 13
1791
10 21
1 13
1791
1 13
10 21
1791
10 13
1 21
1
10 3
1 2
1
1 2
10 3
0
``````
Output:

Code: Select all

``````15 76
76 15
11 120
120 11
15 76
failed
failed
``````

### Re: 10090 - Marbles

Posted: Thu Feb 03, 2011 6:49 pm
@Solaris: welcome back. ### Re: 10090 - Marbles

Posted: Thu May 12, 2011 9:52 pm
Just got an AC. My problem was that my "infinity" constant was not great enough.

Input:

Code: Select all

``````2000000000
2000000000 1
2000000000 2
0
``````
Output:

Code: Select all

``````0 1000000000
``````

### Re: 10090 - Marbles

Posted: Sun Jun 17, 2012 1:40 am
getting WA.
actually my code gives incorrect answer when one of the coefficients in Diophantine equation is equal to 0.
can anyone give me a hint how can i handle that case?

it gives correct output for other test cases.(as far as i checked)

here is my code :

Code: Select all

``````removed after ac.
``````

### Re: 10090 - Marbles

Posted: Tue Feb 19, 2013 11:12 am
Just solved this by pure simulation. However, the ending situation must be decided carefully to prune non-necessary computation to speed up.

### Re: 10090 - Marbles

Posted: Sun Jul 27, 2014 4:45 pm
Why TLE ?
I tested every input given at this forum on this topic, I am getting correct output for every input.
To avoid TLE what should I do?

Code: Select all

``````#include<stdio.h>
int main()
{
int n,c1,n1,c2,n2,m1,m2,rem;
float r1,r2;
while(scanf("%d",&n) && n!=0)
{
scanf("%d %d",&c1,&n1);
scanf("%d %d",&c2,&n2);
r1=(float)c1/n1;
r2=(float)c2/n2;
if(n<n1 && n<n2)
printf("failed\n");
else
{
if(r1<r2)
{
m1=n/n1;
rem=n-m1*n1;
while(rem%n2!=0)
{
m1--;
rem+=n1;
if(m1==0)
break;
}
m2=rem/n2;
}
else
{
m2=n/n2;
rem=n-m2*n2;
while(rem%n1!=0)
{
m2--;
rem+=n2;
if(m2==0)
break;
}
m1=rem/n1;
}
if(m1*n1+m2*n2==n)
printf("%d %d\n",m1,m2);
else printf("failed\n");
}
}
return 0;
}
``````

### Re: 10090 - Marbles

Posted: Mon Jul 28, 2014 8:16 pm