516 - Prime Land

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

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

516 - Prime Land

Post by deddy one » Thu Jan 23, 2003 4:06 pm

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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sun Feb 16, 2003 8:18 pm

forget it, the problem is only at my strtok.

fixed it and get PE

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Feb 21, 2003 8:39 am

yes, be careful while using strtok with while..
and always check for break properly.
"Everything should be made simple, but not always simpler"

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

516re(SIGFPE)

Post by lendlice » Fri Aug 01, 2003 8:39 am

I found where is wrong with my code.
Last edited by lendlice on Tue Aug 05, 2003 7:33 am, edited 1 time in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Fri Aug 01, 2003 9:06 am

RTE SIGSFE is occured when there is division by zero. check your division / mod.
Kalo mau kaya, buat apa sekolah?

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

516 keep on WA

Post by boatfish » Sun Aug 31, 2003 1:52 pm

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]

User avatar
harshahs
New poster
Posts: 8
Joined: Wed Oct 22, 2003 3:58 pm

516 why TLE?

Post by harshahs » Fri Nov 28, 2003 1:04 pm

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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

516WA

Post by Eduard » Tue Jun 22, 2004 5:33 pm

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

some input & output of 516

Post by Rocky » Sun Oct 31, 2004 7:13 am

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
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

516 Prime Land

Post by kenneth » Tue May 10, 2005 1:40 pm

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.
Last edited by kenneth on Sat Sep 03, 2005 3:22 pm, edited 1 time in total.

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Fri May 13, 2005 3:00 am

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:

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth » Sat Sep 03, 2005 3:20 pm

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
New poster
Posts: 2
Joined: Sat Nov 18, 2006 12:56 am

Post by marius_siuram » Sun Nov 19, 2006 11:41 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Nov 22, 2006 5:50 pm

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.
Ami ekhono shopno dekhi...
HomePage

marius_siuram
New poster
Posts: 2
Joined: Sat Nov 18, 2006 12:56 am

Post by marius_siuram » Wed Nov 29, 2006 10:27 pm

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!

Post Reply

Return to “Volume 5 (500-599)”