10104 - Euclid Problem

[vinit_iiita]

TIME LIMIT EXCEEDED. WHY?

Code: Select all

#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int gcd (int p,int q)       //gcd function running fine 
{
    int t;
    if (p==0 || q==0)
    {if (p==0)
     return q;
     else
     return p;
     }
    if (q>p)
    {t=p;
    p=q;
    q=t;
    }
    while (q>0)
    {
          t=q;
          q=p%q;
          p=t;
          }
          return p;
          }
          
int main()
{
    int a,b;
    while (cin>>a>>b)
    {
          int d,x,y=1,m,n;
          bool flag=true,flag1,f=false;
          d=gcd(a,b);
          if(a!=0 && b!=0)
          flag1=true;
          if(a==0 && b==0)
          f=true;
          if(f!=true){
          while (flag==true)
          {if(a!=0 && b!=0)
          {       
           if (((d-b*y)%a)==0)
          {x=((d-b*y)/a);
           flag=false;
          }
          y++;
          }
          else
          {x=0;
          y=2;
          flag=false;
          }
          }
          int x1,y1=-1;
        
          while (flag1==true)
          {
          if (((d-b*y1)%a)==0)
          {x1=((d-b*y1)/a);
           flag1=false;
          }
          y1--;
          }
          
          if(abs(x)+abs(y)<=abs(x1)+abs(y1))
          cout<<x<<" "<<y-1<<" "<<d<<endl;
          else
          cout<<x1<<" "<<y1+1<<" "<<d<<endl;
          }
          else
          cout<<"0"<<" "<<"0"<<" "<<"0"<<endl;
          }
          return 0;
          }

[b][/b][b][/b]

[898989]

Salamo Aleko
This is a known algorithm, i used it as it is....
Its recursive calls will do every thing...Just print ....No compare, no check just ouput...HMHMHM

[taskin]

yes, nothing additional is needed after this algorithm. but i made a small mistake in my implementation after rechecking & now its AC.

[taskin]

correction of previous post :
"but i made a small mistake in my implementation & after rechecking now its AC."
im in sleepy mind.

[kn]

input :
0 5
89 56
89 446
1555 169777
150 3005

output :
0 1 5
17 -27 1
-5 1 1
-21072 193 1
-20 1 5

Hope it helps...

Second requirement in the problem is "X <= Y"
But the 3rd output violates that....

[wjomlex]

Code: Select all

Removed after ACC

I'm getting TLE. I thought it might be because of the iterative form of Euclid's algorithm, but it shouldn't be any slower than the recursive form. Does this problem have a really large input that isn't kind to Java users?

[mf]

java.util.Scanner is generally a very slow class.
Try to replace with StringTokenizer and BufferedReader.

[wjomlex]

I know that Scanner's slow, but somehow I doubt that it's the bottleneck in this problem. Usually Scanner is only an issue in problems that have a lot of input per case, like graph or map problems. But, I'll give it a shot ^_^

I wish I didnt' have to though. In any real contest, Scanner works just fine... UVa should allot extra time for Java like PKU's judge.

[wjomlex]

What do you know? It works with BufferedReader in 2.870s. That's really pushing it.

[arifcsecu]

IT is one of the easiest problem in UVA
Nothing is minimal or ordered here

Just take input
and
run extended_euclid algorithm
link:http://en.wikipedia.org/wiki/Extended_E ... _algorithm

print the triples


ok

i think u will get accepted now

[amishera]

what would be the output for

0 0?

would it be nothing or a blank line?

[helloneo]

what would be the output for

0 0?

would it be nothing or a blank line?

My AC code prints

1 0 0

But I doubt that there is an input like that..

[asif3058]

#include<stdio.h>
#include<iostream>

using namespace std;


int gcd(int a,int b,int &x,int &y)
{
if(a==0)
{
x=0;
y=1;
return b;
}
int x1,y1;
int d=gcd(b%a,a,x1,y1);
x=y1-(b/a)*x1;
y=x1;
return d;
}

int main()
{
// freopen("in.txt","r",stdin);

int a,b;

while(scanf("%d %d",&a,&b)!=EOF)
{
int x,y,d;
d=gcd(a,b,x,y);

printf("%d %d %d\n",x,y,d);


}
}


why WA? here i use extended euclid method.

[brianfry713]

It looks like you figured it out

[lnr]

Got AC