Page 1 of 2

516 - Prime Land

Posted: Thu Jan 23, 2003 4:06 pm
by deddy one
help, pls check my code

[cpp]#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define max 35000

int count [max];
main () {
long int i,j,m,last;
char line[10000];
char *p;
long root;
int input [max];

while (gets (line)) {
if (strcmp (line,"0") == 0) break;
memset (input,0,sizeof (input));
memset (count,0,sizeof (count));
i = 0;
p = strtok (line," ");
input[i++] = atoi(p);
while (p!= NULL)
{
p = strtok (NULL," ");
input[i++] = atoi (p);
}
i--;
m = 1;

for (j=0;j<i;j+=2)
{
m *= (pow(input[j],input[j+1]));
}
m--;
last= 0;
root = (long int)sqrt (m);
for (i=2;;i++)
{
if (i>last) last = i;

if (i > root ) {count[m]++;last = m;break;}

while (!(m%i)) {
count ++;
m /= i;
}
if (m==1) break;
}
for (i=last;i>=0;i--)
{
if (count !=0)
printf ("%ld %d ",i,count);
}
printf ("\n");
}
return 0;
}[/cpp]

Posted: Sun Feb 16, 2003 8:18 pm
by deddy one
forget it, the problem is only at my strtok.

fixed it and get PE

Posted: Fri Feb 21, 2003 8:39 am
by anupam
yes, be careful while using strtok with while..
and always check for break properly.

516re(SIGFPE)

Posted: Fri Aug 01, 2003 8:39 am
by lendlice
I found where is wrong with my code.

Posted: Fri Aug 01, 2003 9:06 am
by titid_gede
RTE SIGSFE is occured when there is division by zero. check your division / mod.

516 keep on WA

Posted: Sun Aug 31, 2003 1:52 pm
by boatfish
I really don't know why this code keeps on WA.
It passes all test cases that I can think about.
[cpp]#include<iostream>
#include<string>
#include<math.h>
using namespace std;

struct src{
int p;
int e;
};
src table[32768];

void factor(int result){
int limit=sqrt(result),no=0,i,t=0;
for(i=2;i<=limit;i++,no=0){
if(result%i==0){
(table[t]).p=i;
while(result%i==0){
result/=i;
no++;
}
(table[t]).e=no;
t++;
}
}
t--;
if(result!=1){
cout<<result<<" 1";
return;
}
for(i=t;i>=0;i--)
cout<<(table).p<<' '<<(table).e<<' ';
}

int main(){
string t;
int i,result,length,e,p,end;
while(getline(cin,t)){
if(t=="0")
break;

result=1;
length=t.length();
for(i=0;i<length;){
end=t.find(' ',i);
p=atoi((t.substr(i,end-i)).c_str());
i=end+1;
end=t.find(' ',i);
if(end!=string::npos){
e=atoi((t.substr(i,end-i)).c_str());
i=end+1;
}
else{
e=atoi((t.substr(i)).c_str());
result*=pow(p,e);
break;
}
result*=pow(p,e);
}

result--;
factor(result);
cout<<endl;
}
return 0;
}
[/cpp]

516 why TLE?

Posted: Fri Nov 28, 2003 1:04 pm
by harshahs
I am getting correct solution for all the input between 3 and INT_MAX, that too instantly, with this code for 516. why OJ is giving TLE?
please help.

[c]
#include <stdio.h>
#include <math.h>
#include <string.h>

unsigned stack[100];

int main(void)
{
char str[80];
unsigned register base,exp,i,val,temp;

while(1)
{
gets(str);

val = 1;


if(strcmp(str,"0")==0)
return 0;

i = 0;

while(str >= '0' && str <= '9')
{
base = 0;

while(str != ' ')
{
base = base*10 + (str - '0');
i++;
}
i++;
exp = 0;

while(str != ' ' && str)
{
exp = exp*10 + (str - '0');
i++;
}
i++;

val *= (unsigned)pow(base,exp);
}
val--;

temp = (unsigned)sqrt(val);
temp++;
exp = 0,i=0;

while(!(val%2))
{
exp++;
val /= 2;
}
if(exp)
{
stack[i++] = 2;
stack[i++] = exp;
}

base = 3;

while(val != 1 || base <= temp)
{
exp = 0;

while(!(val%base))
{
exp++;
val /= base;
}

if(exp)
{
stack[i++] = base;
stack[i++] = exp;
}
base += 2;
}
if(val != 1)
{
stack[i++] = val;
stack[i++] = 1;
}
printf("%d %d",stack[--i],stack[--i]);
while(i)
{
printf(" %d %d",stack[--i],stack[--i]);
}
printf("\n");
}
return 0;
}

[/c]

516WA

Posted: Tue Jun 22, 2004 5:33 pm
by Eduard
Can somebody give me some test cases.I can't understand why I'm getting WA.
[pascal]label 1;
var a:array[0..41000] of byte;
s,i,j,k,n,p:longint;
function parz(n:longint):boolean;
var i:longint;
begin
parz:=true;
for i:=2 to trunc(sqrt(n)) do
if n mod i= 0 then
begin
parz:=false;
break;
end;
end;
procedure solve(n:longint);
var i,j,g:longint;
begin
i:=trunc(sqrt(n));
i:=i+1;
repeat
i:=i-1;
if a=1 then
if n mod i=0 then
begin
g:=0;
repeat
if n mod i=0 then begin g:=g+1;n:=n div i;end;
until n mod i<>0;
write(i,' ',g,' ');
end;
until (n=1);
end;
begin
a[0]:=0;
a[1]:=0;
for i:=2 to 40000 do
if parz(i) then a:=1 else a:=0;
repeat
s:=1;
while not eoln do
begin
read(p);
if p=0 then goto 1;
read(j);
k:=1;
for i:=1 to j do
k:=k*p;
s:=s*k;
end;
readln;
s:=s-1;
solve(s);
writeln;
until 1=2;
1:
end.
[/pascal]

some input & output of 516

Posted: Sun Oct 31, 2004 7:13 am
by Rocky
input:
18 1 17 1 15 1
17 1 11 1
11 1 29 1 9 1
2 1 4 1 5 1 7 1 11 1
18 1 23 1 29 1
31 1 29 1
2 3 11 2 25 1
41 2
51 1 5 1
17 1 19 1 23 1
0
output:
code:
353 1 13 1
31 1 3 1 2 1
41 1 7 1 5 1 2 1
3079 1
7 4 5 1
449 1 2 1
3457 1 7 1
7 1 5 1 3 1 2 4
127 1 2 1
619 1 3 1 2 2

i could not understand your pascel code.by the way this is the output of my accepted code for following input.try now.it might help you BY

516 Prime Land

Posted: Tue May 10, 2005 1:40 pm
by kenneth
Hi, I have developed the solution for this question and have tested it with all numbers from 2 to 32767. Checked the prime factorization is correct. I have printed them out in descending order as well. (I have written a few codes to test these properties). However, the online judge still said my answer is incorrect. I really can't see why my answer is incorrect.

Would anyonen be able to identify the reason for me??

Thanks


Code removed after AC.

Posted: Fri May 13, 2005 3:00 am
by sahand
You're not initializing the 'count' variable in genFac() function.

You should always initialize variables unless they are global, or static.

And, the way you start your program:

Code: Select all

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <stdio.h>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)
is not good at all. I think most C++ programmer's agree with me on these points:
- Don't include headers if you don't need them.
- Don't use macros in that way.

Hope it helped :wink:

Posted: Sat Sep 03, 2005 3:20 pm
by kenneth
Thanks a lot for your help.

I did not realize I have not initialize the value >.< (but it's strangely that I still got the right answer on my own compiler....)

The reason I put all header files in is to such that I don't have to type them up one by one when I try different questions =)

Posted: Sun Nov 19, 2006 11:41 pm
by marius_siuram
I tried with this test cases, with my own ones, and the examples and it seems to me that it runs well, but the judge says an WA.

Code: Select all

#include <iostream>
#include <sstream>
#include <string>

#define MAXPRIME 181
#define MAXTERMS 30

using namespace std;

// these primes are the necessary ones (there are few)
// from 2 to the sqrt of the maximum
int LISTPRIMES[] = { 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 , 101 , 103 , 107 ,
  109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 999};
  // last one indicates end of everything


// reducing the number is more efficient (easier to work with smaller numbers)
// that's why *orig is changed and passed by reference
int numfactors (int * orig , int factor)
{
  int n;
  n = 0;
  while ( *orig % factor == 0 )
  {
    *orig = *orig / factor;
    n++;
  }
  return n;
}

void addfactor (int * orig, int factor, int exp)
{
 
  for ( ;  exp > 0 ; exp-- )
  {
    *orig = *orig * factor;
  }
 
}

int main ()
{
  string oneline;
  int number;
  int base, exp, i;
 
  int solution[MAXTERMS],isol;
 
  while ( 1 )
  {
   
    //get each line (one number per line)
    getline (cin , oneline);
    stringstream feeder ( oneline );
   
    //make the number
    number = 1;
    while ( !feeder.eof () )
    {
      feeder >> base;
      // zero -> exit
      if ( base == 0 ) return (0);
     
      feeder >> exp;
     
      addfactor (&number, base, exp);
    }
   
    // now do the minus 1 and proceed to factorize
    number--;
    isol = 0;
   
   
    i = 0;
    while ( ( LISTPRIMES[i] < MAXPRIME+1 ) && ( (LISTPRIMES[i]*LISTPRIMES[i]) < number ) )
    {
      if ( number % LISTPRIMES[i] == 0 )
      {
        solution[isol] = LISTPRIMES[i];
        solution[isol + 1] = numfactors ( &number , LISTPRIMES[i] );
        isol+=2;
      }
     
      i++;
    }
   
    // if number is still big then it must be a prime
    if ( number > 1 )
    {
      solution[isol] = number;
      solution[isol + 1] = 1;
      isol +=2;
    }
   
    // now we have to print inverting the order
    isol -= 2;
    cout << solution[isol] << " " << solution[isol + 1];
    isol -= 2;
   
    for ( ; isol > -1 ; isol -= 2 )
    {
      cout << " " << solution[isol] << " " << solution [isol + 1];
    }
   
    cout << endl;
   
  }
 
  return (0);
}
Well ... some silly thing maybe? I suppose that primes until 181 are quite enough (the text of 516 says that the number to do the minus one will be less or equal than 32767, and 181 is its sqrt). I was too lazy to implement a cribe of erathostenes (or however it is spelled).

Posted: Wed Nov 22, 2006 5:50 pm
by Jan
I have made a file consisting of Rocky's input. And ran your code. Your code didnot pass the samples. But when I gave input by hand your code produced right. Just make a input file and run your code. You have to fix it.

Posted: Wed Nov 29, 2006 10:27 pm
by marius_siuram
mmmm wow, thanks. I see then, something weird is happening, and I didn't expect that type of problem (something with the endlines-code or similar). I'll fix that soon I hope.

Thanks a lot!