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

Martuza_cseiu
New poster
Posts: 2
Joined: Mon Mar 28, 2011 5:49 am

11827

Post by Martuza_cseiu » Thu Jun 23, 2011 1:33 pm

At last I got AC...........

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm
Location: Dhaka, Bangladesh.

11827 - Maximum GCD (Why RE??)

Post by MAMU » Sat Jun 25, 2011 3:37 pm

Code: Select all

AC
Last edited by MAMU on Mon Jul 11, 2011 7:28 pm, edited 1 time in total.

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

Re: 11827 - Maximum GCD (Why RE??)

Post by sohel » Sat Jun 25, 2011 11:42 pm

As the memory for local variables is allocated in stack, you can't declare such a huge array inside a function.
Try allocating the memory in heap using the new operator or make the array global.

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm
Location: Dhaka, Bangladesh.

Re: 11827 - Maximum GCD (RE again)

Post by MAMU » Sun Jun 26, 2011 10:58 am

Code: Select all

AC
Last edited by MAMU on Mon Jul 11, 2011 7:30 pm, edited 1 time in total.

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm
Location: Dhaka, Bangladesh.

Re: 11827 - Maximum GCD (Why RE??)

Post by MAMU » Thu Jun 30, 2011 6:08 pm

Someone please reply......

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11827 - Maximum GCD (Why RE??)

Post by plamplam » Tue Jul 05, 2011 5:10 pm

I got 3 Runtime Errors before I finally got AC so here are some reasons you can get Runtime error.

1. Your Array size is not big enough (100000 is enough).
2. The judge data contains inputs with 0. My first approach was to find the minimum and maximum of the two numbers. So then I check if max % min == 0 then the GCD equals the lesser number. If not then I apply brute force to calculate the GCD. The reason I got runtime error was min can be 0 :D So make sure your program can handle cases like 0 1 2 3 etc.
3. Try this input:
1
10 20 30 40(space)(space)(space)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11827 - Maximum GCD (Why RE??)

Post by plamplam » Tue Jul 05, 2011 5:12 pm

Mamu I checked your program...your code doesn't output anything for my test case.
1
10 20 30 40(space)(space)(space).
Hope it helps you. :wink: :roll:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm
Location: Dhaka, Bangladesh.

Re: 11827 - Maximum GCD (Why RE??)

Post by MAMU » Mon Jul 11, 2011 7:34 pm

Sorry, I'd got AC before I saw your post but I forgot to remove the post.
plamplam, I think my problem was getting the numbers from the input string.

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 11827 - Maximum GCD (Why RE??)

Post by mathgirl » Sun May 20, 2012 12:33 pm

I m constantly getting TLE on this one. Any better algo ?

Code: Select all

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

using namespace std;

int main()
{
	int t,re;
	re = scanf("%d",&t);
	while(t--)
	{
		int a,lowest = INT_MAX;
		vector<int> input;
		getchar();
		while(cin.peek() != '\n')
		{
			re = scanf("%d",&a);
			input.push_back(a);
			lowest = min(lowest,a);
		}

		bool valid = true;
		for(lowest;lowest >= 2;lowest--)
		{
			valid = true;
			for(int i = 0;i < input.size();i++)
			{
				if(input[i] % lowest != 0)
				{	
					valid = false;
					break;
				}
			}

			if(valid)
				break;
		}

		printf("%d\n",lowest);
	}
	return 0;
}

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

Re: 11827 - Maximum GCD (Why RE??)

Post by brianfry713 » Tue May 22, 2012 2:32 am

Doesn't match the sample I/O.

Don't use getchar() and count on it to read a newline. Instead write something like:
while(getchar()!='\n');

Your code goes into an infinite loop if there are trailing spaces on a line.
Check input and AC output for thousands of problems on uDebug!

sornaCse
New poster
Posts: 6
Joined: Thu Jul 26, 2012 9:40 am

11827 Why WA?

Post by sornaCse » Thu Jul 26, 2012 9:45 am

Code: Select all

thank you sir! i got rank 57 with 0.004s :D 
Last edited by sornaCse on Fri Jul 27, 2012 8:37 am, edited 1 time in total.

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

Re: 11827 Why WA?

Post by brianfry713 » Fri Jul 27, 2012 1:26 am

Reset flag at the beginning of numbers()
Check input and AC output for thousands of problems on uDebug!

raihan004
New poster
Posts: 2
Joined: Tue Oct 09, 2012 2:07 am

11827 - Maximum GCD Getting Wrong Ans Need Help

Post by raihan004 » Thu Oct 25, 2012 2:06 am

hi am (11827 - Maximum GCD) Getting Wrong Ans Need Help. I dont know where is my fault. pls me help me to find my fault.
here is my code

Code: Select all

#include<stdio.h>
int main()
{
    int s,t;
    scanf("%d",&t);
    for(s=0;s<t;s++)
    {
        long long max=0,a[1000000],n,p,q;
        int i,j,m;
        char c;
        m=0;
        do
        {
            scanf("%lld%c",&a[m],&c);
            m++;
        }
        while(c==' ');
        for(i=0;i<m;i++)
    {
          for(j=i+1;j<m;j++)
        {
            p=a[i];
            q=a[j];
            while(q!=0)
            {
                n=p%q;
                p=q;
                q=n;
            }
            if(max<=p)
            max=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 Getting Wrong Ans Need Help

Post by brianfry713 » Fri Oct 26, 2012 12:28 am

Your code doesn't match the sample I/O when I tested it. Try reading the input a line at a time.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 11827 Why WA?

Post by shuvokr » Fri Feb 22, 2013 11:55 am

Code: Select all

AC ...

Code: Select all

enjoying life ..... 

Post Reply

Return to “Volume 118 (11800-11899)”