11827 - Maximum GCD

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

Moderator: Board moderators

KAI10
New poster
Posts: 2
Joined: Thu Dec 05, 2013 5:10 pm

11827 - Maximum GCD

Post by KAI10 » Wed Jan 29, 2014 6:59 pm

Hello, i,m getting runtime error for this code. can any body point out the bug please. really need help .....

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11827 maximum GCD

Post by brianfry713 » Wed Jan 29, 2014 11:27 pm

Your code is throwing a divide by 0 (b = 0) on line 6 running the sample input:
if (a%b==0) return b;
Check input and AC output for thousands of problems on uDebug!

KAI10
New poster
Posts: 2
Joined: Thu Dec 05, 2013 5:10 pm

Re: 11827 maximum GCD

Post by KAI10 » Thu Jan 30, 2014 10:25 am

thanks, i got rid of RE. But now i am getting WA :x . please help........

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (!b) return a;
    if (!a) return b;
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11827 maximum GCD

Post by brianfry713 » Thu Jan 30, 2014 10:28 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11827 maximum GCD

Post by uDebug » Wed May 14, 2014 8:49 am

Here's some input / output that I found useful during testing / debugging.

Note that the judge's input does not have a case like the 4th one below but I think it makes sense to handle this, so, I threw it in.

Input:

Code: Select all

4
     45      20     30        40 100          10000        1500
  13                20                    93     31         
     0   99          
              0                         
AC Output:

Code: Select all

500
31
99
0
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 11827 - Maximum GCD

Post by LazyTym » Thu Oct 30, 2014 12:20 am

Why getting WA?????????????i think it's an easy problem bt i can not find the bug...........pls help.......

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;

int EUCILD(int a,int b) {
    if(b==0) return a;
    else EUCILD(b,a%b);
}

int main()
{
    int A[101];
    int t,a;
    cin>>t;
    while(t--) {
        int i=0,c;
        int p,maximum=0;
        char ch;
        do
        {
            scanf("%d%c",&A[i],&ch);
            i++;
        }
        while(ch==' ');
        c=i--;

        for(int i=0;i<c-1;i++) {
            for(int j=i+1;j<c;j++) {
                if(A[i]<A[j]) {
                   p=EUCILD(A[j],A[i]);
                }
                else {
                   p=EUCILD(A[i],A[j]);
                }
                if(maximum<p) maximum=p;
            }
        }
        cout<<maximum<<endl;
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11827 - Maximum GCD

Post by brianfry713 » Thu Oct 30, 2014 9:39 pm

Your code doesn't work on the sample input. Try parsing the input line by line and then use something like strtok or stringstream to extract the tokens of each line.
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 11827 - Maximum GCD

Post by richatibrewal » Tue Dec 09, 2014 3:38 pm

Hii,the following code got accepted for 0.015 s. How can I improve this code ?

Code: Select all

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int n,a[200]={0},i,j,max=-1,l,len,flag,g;
    char s[100096];
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        j=-1;
        max=-1;
        flag=1;
        fgets(s,100096,stdin);
        for(i=0;i<=strlen(s)-1;i++)
        {
            if(s[i]==' ')
            {
                flag=1;
                continue;
            }
            if((flag==1)||(i==strlen(s)-1))
            {
                a[++j]=0;
                flag=0;
                for(len=j-2;len>=0;len--)
                {
                    g=gcd(a[j-1],a[len]);
                    if(g>max)
                        max=g;
                }
            }
            if(i<strlen(s)-1)
            {
                l=s[i]-48;
                a[j]=(10*a[j])+l;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}

Post Reply

Return to “Volume 118 (11800-11899)”