10090  Marbles
Moderator: Board moderators
Re: 10090  Marbles
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+y1)/y.
(The '/' on righthand 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.
(The '/' on righthand 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
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)
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
Oh, right, sorry about that.
I've edited my post to fix that, so that it won't confuse somebody else.
I've edited my post to fix that, so that it won't confuse somebody else.
Re: 10090  Marbles
Can anyone tell me why the answer is wrong?
input
133356304
1870 8365
2572 3204
output
3076 33591
my code:
If you can say where is my mistake i will be thankful
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[i1].y;
eq1[i].y = (long long int)eq1[i1].x  (Pa[tami+2]/Pb[tami+2]) * eq1[i1].y;
}
tam = i1;
}
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");
}
}
}

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 10090  Marbles
Try this: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
Code: Select all
100
1 2
2 4
100
2 2
1 4
133356304
1870 8365
2572 3204
0
Code: Select all
0 25
0 25
15892 131
Mak
Help me PLZ!!
Help me PLZ!!

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
Re: 10090  Marbles
Try these
Input:
Output:
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
Code: Select all
15 76
76 15
11 120
120 11
15 76
failed
failed
Where's the "Any" key?
Re: 10090  Marbles
Just got an AC. My problem was that my "infinity" constant was not great enough.
Input:
Output:
Input:
Code: Select all
2000000000
2000000000 1
2000000000 2
0
Code: Select all
0 1000000000

 New poster
 Posts: 31
 Joined: Thu Nov 24, 2011 12:08 am
Re: 10090  Marbles
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 :
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

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 10090  Marbles
Just solved this by pure simulation. However, the ending situation must be decided carefully to prune nonnecessary computation to speed up.
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?

 Experienced poster
 Posts: 148
 Joined: Sun Jul 13, 2014 4:32 am
 Location: Rangpur, Bangladesh
Re: 10090  Marbles
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?
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=nm1*n1;
while(rem%n2!=0)
{
m1;
rem+=n1;
if(m1==0)
break;
}
m2=rem/n2;
}
else
{
m2=n/n2;
rem=nm2*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;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felixhalim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felixhalim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10090  Marbles
Read this thread. Don't use floating point in this problem.
Check input and AC output for thousands of problems on uDebug!