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+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.
(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
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[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");
}
}
}
-
- 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 non-necessary 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 real-world 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=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;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.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.felix-halim.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!