Page **3** of **3**

### Re: 10090 - Marbles

Posted: **Fri Dec 12, 2008 10:02 am**

by **mf**

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

by **fR0D**

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

by **mf**

Oh, right, sorry about that.

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

by **Pedro**

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[100], Pb[100];
long long int cust1,cust2,cap1,cap2,qt,d;
struct val eq1[100], eq2[100];
//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[1].x = (long long int)x;
eq1[1].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**

by **Pedro**

up

### Re: 10090 - Marbles

Posted: **Fri Jun 12, 2009 5:28 am**

by **roticv**

use %lld

### Re: 10090 - Marbles

Posted: **Wed May 19, 2010 7:41 pm**

by **mak(cse_DU)**

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:

### Re: 10090 - Marbles

Posted: **Thu Feb 03, 2011 2:17 pm**

by **Solaris**

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

by **sohel**

@Solaris: welcome back.

### Re: 10090 - Marbles

Posted: **Thu May 12, 2011 9:52 pm**

by **Karolis**

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:

### Re: 10090 - Marbles

Posted: **Sun Jun 17, 2012 1:40 am**

by **mostafiz93**

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.
made a silly mistake
```

### Re: 10090 - Marbles

Posted: **Tue Feb 19, 2013 11:12 am**

by **DD**

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

by **Shahidul.CSE**

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

by **brianfry713**

Read this thread. Don't use floating point in this problem.