160 - Factors and Factorials

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

Moderator: Board moderators

kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm

Post by kwedeer »

Thaks little joey now Accepted... But how could I know this?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I don't know. I think on unix systems the newline is used as a line terminator rather than as line separator, which means that all lines, including the last, should end with a newline; my linux compiler complains if my source doesn't end in a newline, but my DOS compiler doesn't.

Anyway, just always terminate your lines, and if the output format specifies that you should print a blank line after the last case (some problems do that), just use an extra writeln:
writeln(last line of output);
writeln;

Rhododendron
New poster
Posts: 1
Joined: Sun Jun 18, 2006 7:34 am

Post by Rhododendron »

Why you the guy's upload your code.Let us discuss about the algorithm.
If any one does not know how to use algorithm then he/she should leave
programming.

TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

160 - RUNTIME ERROR!!

Post by TripShock »

this code works for all test cases on my pc, but with oj it give runtime error floating point exception! somebody please help!

info:
i use sieve of eratosthenes to compute all prime nos >=2 <= 100.

Code: Select all

ACCEPTED!!
Last edited by TripShock on Fri Jun 23, 2006 1:42 am, edited 1 time in total.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

Its ok that you got RTE.
But if you use formula then you must get accepted:).

Code: Select all

Highest Power of a prime (P) which divides (n!) is
floor(n/p)+floor(n/p^2)+floor(n/p^3) +........+floor(n/p^h)
where p=2,3,5,7....etc

so you can do it easily with repeated division like 10!.
10/2=5
5/2=2
2/2=1
Hope you now Clear :)

TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

Post by TripShock »

That's a really cool method! Thanks! But I still don't get why the oj flags runtime error for my original program!

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

hope this will help you.
This is my SIEVE CODE. You define ur array Size.ok.

Code: Select all

int p[SIZE];
int k;
void prime(long SIZE)
{
	int i,j;
	bool *pr=new bool[SIZE+10];
	for(i=2;i<=MAX;i++){pr[i]=true;}
	for(i=2;i<=MAX;i++){if(!pr[i]) continue;for(j=i+i;j<=MAX;j+=i){pr[j]=false;}}
	k=0;
	for(i=2;i<=MAX;i++){if(pr[i]){p[k++]=i;}}
	delete [] pr;
}
Hope its Help.

TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

Post by TripShock »

I don't know what but something about your sieve code is just SOO right, asif_rahman! thanks a lot! i don't know how but your code got my program accepted!

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

160

Post by abhi »

hey this is my code for this simple problem ............. but i get TLE ..........
why ?????

Code: Select all


CODE DELETED after AC :)


Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

160 - Dont Understand

Post by Donotalo »

how does the first output for 53! is 49? probably i dont understand the representation. can anyone explain it to me?
Image

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania

Post by nev4 »

825 could be specified as (0 1 2 0 1) meaning no twos, 1 three, 2 fives, no sevens and 1 eleven.


This problem is so easy to solve, but I don't know why WA, even if I think it works just fine. Anyone can help me?

Code: Select all

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

int rez[99]; // times of primes

int main()
{
	vector<int> primes;
	primes.push_back(2);
	primes.push_back(3);
	vector<int>::iterator it;
	for(int i = 5; i < 100; i++)
	{
	    for(it = primes.begin(); it != primes.end(); ++it)
	    {
	        if(i % *it == 0)
	        {
	            break;
	        }
	    }
	    if(it == primes.end())
	    {
	        primes.push_back(i);
	    }
	}
	int n;
	cout.setf(ios::right);
	while(cin >> n)
	{
	    if(n == 0)
	    {
	        return 0;
	    }
	    for(int i = 0; i < 99; i++)
	    {
	        rez[i] = 0;
	    }
	    for(int i = 2; i <= n; i++)
	    {
	        int j = i;
	        for(it = primes.begin(); *it <= n; ++it)
	        {
	            while(j % *it == 0)
	            {
	                ++rez[*it];
	                j /= *it;
	            }
	            if(j == 1)
	            {
	                break;
	            }
	        }
	    }
	    cout << setw(3) << n << "! =";
	    int count = 0;
	    for(it = primes.begin(); *it <= n; ++it)
	    {
	        if(count % 15 == 0 && count)
	        {
                cout << endl << setw(9) << rez[*it];
	        }
	        else
	        {
	            cout << setw(3) << rez[*it];
	        }
	        ++count;
	    }
	    cout << endl;
	}
	return 0;
}

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

sorry to bother again....... :( got WA but hav no idea whyyyyyy????
everything seems to be so perfect..read all prev threads too and thus got sure abt my output format....then where is the mistake?can any1 say :(
i'm getting frustrated.


Code: Select all

removed
maybe the mistake is silly...but in return wat i'm getting is not so silly...
so thanx in advance
Last edited by kolpobilashi on Wed Aug 16, 2006 4:30 pm, edited 1 time in total.
Sanjana

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Code: Select all

printf("\n      ");
Above statement will be executed for any N. But it should be executed for those only whose factorial have more than 15 prime factors.

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

thanx a lt bro...the mistake is in the 2nd for loop condition....how cud i be so stupid :oops:

thanx again. :)
Sanjana

srabon
New poster
Posts: 4
Joined: Thu Aug 10, 2006 3:27 pm

ACM 160 I get WA many time , I do not Why, please healp me

Post by srabon »

code deleted
Last edited by srabon on Tue Aug 29, 2006 6:44 am, edited 1 time in total.

Post Reply

Return to “Volume 1 (100-199)”