516 - Prime Land

[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]

[deddy one]

forget it, the problem is only at my strtok.

fixed it and get PE

[anupam]

yes, be careful while using strtok with while..
and always check for break properly.

[lendlice]

I found where is wrong with my code.

[titid_gede]

RTE SIGSFE is occured when there is division by zero. check your division / mod.

[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]

[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]

[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]

[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

[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.

[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

[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 =)

[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).

[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.

[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!