10104 - Euclid Problem

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita » Tue Jul 04, 2006 10:33 pm

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]
win

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Fri Jul 14, 2006 8:38 pm

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 :lol:
Sleep enough after death, it is the time to work.
Mostafa Saad

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

Post by taskin » Fri Jul 14, 2006 10:19 pm

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

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

Post by taskin » Fri Jul 14, 2006 10:23 pm

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

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Mon Jul 30, 2007 6:20 pm

jan_holmes wrote:
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... :D
Second requirement in the problem is "X <= Y"
But the 3rd output violates that....

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 10104 - Euclid Problem

Post by wjomlex » Fri Dec 19, 2008 1:59 am

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?
Last edited by wjomlex on Fri Dec 19, 2008 8:44 pm, edited 1 time in total.

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

Re: 10104 - Euclid Problem

Post by mf » Fri Dec 19, 2008 7:17 pm

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

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 10104 - Euclid Problem

Post by wjomlex » Fri Dec 19, 2008 7:37 pm

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
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 10104 - Euclid Problem

Post by wjomlex » Fri Dec 19, 2008 8:43 pm

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

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 10104 - Euclid Problem

Post by arifcsecu » Wed Sep 30, 2009 9:38 pm

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
Try to catch fish rather than asking for some fishes.

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10104 - Euclid Problem

Post by amishera » Tue Jun 08, 2010 11:42 pm

what would be the output for

0 0?

would it be nothing or a blank line?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10104 - Euclid Problem

Post by helloneo » Sun Jun 13, 2010 4:48 pm

amishera wrote: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
New poster
Posts: 1
Joined: Tue Mar 05, 2013 8:02 am

Re: 10104 - Euclid Problem

Post by asif3058 » Sat Jan 04, 2014 11:00 am

#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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10104 - Euclid Problem

Post by brianfry713 » Wed Jan 15, 2014 12:53 am

It looks like you figured it out
Check input and AC output for thousands of problems on uDebug!

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 10104 - Euclid Problem

Post by lnr » Wed Jun 12, 2019 1:27 pm

Got AC

Post Reply

Return to “Volume 101 (10100-10199)”