10090 - Marbles

[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.

[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)

[mf]

Oh, right, sorry about that.

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

[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

[Pedro]

up

[roticv]

use %lld

[mak(cse_DU)]

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

[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

[sohel]

@Solaris: welcome back.

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

Code: Select all

0 1000000000

[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 

[DD]

Just solved this by pure simulation. However, the ending situation must be decided carefully to prune non-necessary computation to speed up.

[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;
}

[brianfry713]

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