Page 13 of 14

Re: 160 - Factors and Factorials

Posted: Mon Jul 19, 2010 1:11 am
by il_demente
My problem here is more like an inquiry. You see i wrote a code that calculated the prime factors of all numbers at the beginning of the main function and starts taking input and outputs the related answer. When i submitted this code i got WA i checked the code for any possible reason of getting the WA but i couldn't find one thing that would justify this WA. So after i gave up debugging, i deleted all the code and started a new one where i calculated the prime factors of each number that is inputed and i got AC.

It rose my suspicion so i tried to check for the output of both codes that i wrote so i generated all the numbers from 2 to 100 as stated in the problem set and saved the output of both codes in an external file. I compared the output of both files using a program i have and i found that the were the same no extra white spaces, nothing. They were the same

My question is what is the reason that the judge rejected the first code, yet it accepted the other code even though they generate the same output for the stated input.

the AC code:

Code: Select all

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int primesFactors[100]; 
void primeFactorization(int input) 
{ 
	for(int j=2; j<=input; j++)
	{
	int number = j;
		while ((number % 2) == 0)
		{
			primesFactors[2]++;
			number = number / 2; 
		}
		int i = 3; 

		while (i*i <= (number) + 1) 
		{ 
			if ((number % i) == 0) 
			{ 
				primesFactors[i]++;
				number /= i; 
			} 
			else i = i + 2; 
		} 
		if (number > 1) 
			primesFactors[number]++; 
	}
}
int main()
{
	int input;
	while(cin >> input && input)
	{
		memset(primesFactors, 0, sizeof primesFactors);
		primeFactorization(input);
		printf("%3ld! =",input);
		for(int j=0, c=0; j<25; j++, c++)
		{	
			if(primes[j]>input)
				break;
			if(c%15==0 && c) 
				printf("\n%6c",' '); 
			printf("%3d",primesFactors[primes[j]]);
		}
		printf("\n");
	}
	return 0;
}

The WA code that generates the answer at the begining:

Code: Select all

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int pFactors[100][100];
int result[100];

void primeFactorization() 
{ 
	memset(pFactors, 0, sizeof(int) * 100 *100 );
	memset(result, 0, sizeof(int) * 100);
	int number;
	for(int j=2; j<=100; j++)
	{
		number = j;
		while ((number % 2) == 0)
		{
			pFactors[j][2]++;
			number /= 2; 
		}

		int i = 3, root = sqrt((double)number) +1; 
		while (i <= root) 
		{ 
			if ((number % i) == 0) 
			{ 
				pFactors[j][i]++;
				number /= i; 
			} 
			else i += 2; 
		} 
		if (number > 1) 
			pFactors[j][number]++;
	}
}

int main()
{
	int input;
	primeFactorization();
	while(cin >> input && input)
	{

		memset(result, 0, sizeof result);

		//These 2 loops iterate through all the primes which are factors of
		//the factorial of the input and add them to the result array
		for(int i=0; i<25; i++)  
			for(int j=2; j<=input; j++)
				result[primes[i]]+= pFactors[j][primes[i]];

		printf("%3ld! =",input);
		for(int j=0, c=0; j<25; j++, c++)
		{	
			if(primes[j]>input)
				break;
			if(c%15==0 && c) 
				printf("\n%6c",' '); 
			printf("%3d",result[primes[j]]);
		}
		printf("\n");

	}
	return 0;
}

160 - Factors and Factorials (WA)

Posted: Sun Apr 24, 2011 6:55 pm
by tuner
my code below
i still cannot find where get wrong
anyone can help me or give me some tips
or some key test case
point what's wrong with my code
THX

Code: Select all

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main ()
{
    int n;
    while ( cin >> n )
    {
        if ( n == 0 )   return 0;
        int fac[n + 1];
        for ( int i = 2; i <= n; i++ )
            fac[i] = 0;
        for ( int i = n; i >= 2; i-- )
        {
            for ( int j = 2; j <= n; j++ )
            {
                int k = i;
                while ( k % j == 0 )
                {
                    fac[j]++;
                    k /= j;
                }
            }
        }
        cout << setw(3) << right << n << "! =";
        for ( int i = 2; i <= n; i++ )
        {
            if ( i == 2 || i == 3 || i == 5 || i == 7 || i == 11 ||
                i == 13 || i == 17 || i == 19 || i == 23 || i == 29 ||
                i == 31 || i == 37 || i == 41 || i == 43 || i == 47 ||
                i == 53 || i == 59 || i == 61 || i == 67 || i == 71 ||
                i == 73 || i == 79 || i == 83 || i == 89 || i == 97 )
            {
                cout << setw(3) << fac[i];
            }
            if ( i == 47 )
            {
                cout << endl << setw(6) << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

160 getting WA

Posted: Sun Jun 19, 2011 10:03 am
by wetcat
my output is right,but why i am getting WA???pls help me...



int prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int m,factor_counter[101];

int find_prime_factor(int a)
{
if(a==1)
return 0;

else if(a%prime[m]==0)
{
factor_counter[prime[m]]++;
find_prime_factor(a/prime[m]);
}
else
{
m++;
find_prime_factor(a);
}

}

int main()
{


int n,temp,i,j,count;
while(cin>>n && n!=0)
{

for(i=0;i<101;i++)
factor_counter=0;
for(i=2;i<=n;i++)
{
m=0;
find_prime_factor(i);
}
cout<<setw(3)<<n<<"! =";
for(int x=3, i=2,count=0;i<99;i++)
{


if(count==15)
{
cout<<endl;
count=0;
x=9;
}
if(factor_counter>0)
{
cout<<setw(x)<<factor_counter;
x=3;
count++;
}
}

cout<<endl;
}
return 0;
}

160 runtime error!

Posted: Tue Jan 24, 2012 1:35 am
by bloodytears67
It crashes after 96 :(

Code: Select all

#include <stdio.h>

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

int main()
{
    int n,i;

    while ((scanf("%d",&n))==1)
    {
        if (n==0) break;

        else
        {
            printf("%3d! =",n);
            int count,temp;
            for (i=0; primes[i]<=n; i++)
            {
                count = 0;
                temp = n;
                while (temp>0)
                {
                    temp/=primes[i];
                    count+=temp;
                }
                if (i == 15) printf("\n%9d",count);
                else printf("%3d",count);

            }

            printf("\n");
        }
    }

    return 0;
}


Re: 160 runtime error!

Posted: Wed Jan 25, 2012 1:15 am
by brianfry713
Add 101 to your list of primes.

Re: 160 runtime error!

Posted: Thu Jan 26, 2012 3:51 am
by bloodytears67
thanks brianfry713 :) it worked :)

Presentation error on 160

Posted: Sun Dec 23, 2012 9:01 am
by happyson10
The code was removed after getting AC

Re: Presentation error on 160

Posted: Sat Dec 29, 2012 12:23 pm
by brianfry713
you've got an extra space after the =

Re: Presentation error on 160

Posted: Thu Jan 03, 2013 12:10 am
by happyson10
oh, got it, thanks a lot

Re: Presentation error on 160

Posted: Tue Jan 08, 2013 11:00 am
by gr81
getting WA, in this case, but passed all my test case...please have a look ..

AC now.

thanks...

Re: Presentation error on 160

Posted: Tue Jan 08, 2013 9:22 pm
by brianfry713
Don't print an extra blank line at the end.

Re: Presentation error on 160

Posted: Wed Jan 09, 2013 7:17 am
by gr81
I removed the new line at the end, but still getting WA.

Re: Presentation error on 160

Posted: Wed Jan 09, 2013 10:03 pm
by brianfry713
Input

Code: Select all

47
48
0
Correct output:

Code: Select all

 47! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1  1
 48! = 46 22 10  6  4  3  2  2  2  1  1  1  1  1  1
Your output:

Code: Select all

 47! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1  1
      
 48! = 46 22 10  6  4  3  2  2  2  1  1  1  1  1  1
      

Re: Presentation error on 160

Posted: Thu Jan 10, 2013 4:04 am
by gr81
thanks brian..
that was kewl input.

Re: Presentation error on 160

Posted: Wed Aug 07, 2013 5:13 am
by techbd123
Why getting WA and printing a newline it's PE???

My code is here. http://pastebin.com/mYH6gGcD

Please reply quickly.