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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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.

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

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)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10090 - Marbles

Oh, right, sorry about that.

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

Pedro
New poster
Posts: 5
Joined: Fri Jul 20, 2007 5:18 pm

Re: 10090 - Marbles

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

Pedro
New poster
Posts: 5
Joined: Fri Jul 20, 2007 5:18 pm

Re: 10090 - Marbles

up

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 10090 - Marbles

use %lld

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

Re: 10090 - Marbles

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
Mak
Help me PLZ!!

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:

Re: 10090 - Marbles

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
Where's the "Any" key?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10090 - Marbles

@Solaris: welcome back. Karolis
New poster
Posts: 1
Joined: Thu May 12, 2011 9:47 pm

Re: 10090 - Marbles

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

mostafiz93
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 :

Code: Select all

removed after ac.
made a silly mistake

DD
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?
If so, you need to read Elements of Programming Interviews.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am

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?

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