## 100 - The 3n + 1 problem

Moderator: Board moderators

Vartanov Daniel
New poster
Posts: 5
Joined: Tue Aug 27, 2002 7:46 pm
Location: Russia
Contact:

### 100 - 3n+1 Problem (SIGSEGV!!!! It can't be!)

6 monthes ago i got AC for this problem!!!
I posted this problem again several hours ago and got SIGSEGV, but i DID NOT change my code!!!

Code: Select all

``````#include <stdio.h>
#include <string.h>

long sol[10001];

void precount()
{
long t;
long c;
for (long i = 1; i <= 10000; i++)
{
c = 0;
t = i;
while (t != 1)
{
if (t % 2) t = 3 * t + 1; else t /= 2;
c++;
}
sol[i] = c;
}
}

int main()
{
int n, m, p, q;
long max = 0;
precount();
while (scanf("%d %d", &n, &m) == 2)
{
max = 0;
if (m>n)
{
p = n;
q = m;
}
else
{
p = m;
q = n;
}
for (int i = p; i <= q; i++)
if (sol[i] > max) max = sol[i];
printf("%d %d %ld\n", n, m, ++max);
}
return 0;
}
``````
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You didn't change your code, but the program has changed. Read the description again :-)
katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:

### problem100

I don't konw what the problem is in my code.
Can any one help me?

Code: Select all

``````#include<stdio.h>
int lengh(long int);
int main(void)
{
long int i,j,a;
int k,c;
while(1)
{
c=0;
scanf("%ld %ld",&i,&j);
if(i==0||j==0)
break;
if(i>j)
{
for(a=j;a<=i;a++)
{  k=lengh(a);
if(k>c)
c=k;
}
printf("%ld %ld %d\n",i,j,c);
}
else
{
for(a=i;a<=j;a++)
{  k=lengh(a);
if(k>c)
c=k;
}
printf("%ld %ld %d\n",i,j,c);
}
}
return 0;
}
int lengh(long int n)
{
int b=1;
if(n==1)
return 1;
while(n>1)
{
if(n%2==1)
n=3*n+1;
else
n=n/2;
b=b+1;
}
return b;
}``````
Thanks!!!!
Last edited by katy on Wed Sep 04, 2002 4:45 pm, edited 1 time in total.
katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:

### sorry!

I'm sorry!
I should told you that the result I got is "time limit exceeded".
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:
so,what can I do to get it better?
New poster
Posts: 3
Joined: Tue Sep 03, 2002 3:31 am

### i found something

your program is not doing anything if i=j
zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### some hints

There is one very common error on this task: preasuming that a<=b it is not true if I remember right.
As fas as having a faster code - may be you could save an array with already computed values. E.g. you will compute length(10) once for 10 10, and one more time for 1 15. That is very stupid for multi input tasks.
Good luck next time.
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com
arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
for more faster code, you could also minimize the calculation progress, by not calculating all the number.
remember:
if cycle[n] = a, then cycle[2n] = a+1, and so on...
using sieve-like technique, you could precalc all the possible number with just a little time
ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
I think that the optimization required for this problem is not that hard. I got AC in this problem without taking too much care about optimization. The only thing is that i use DP, explicitly Memoization.

Hope this can help.

PS: Before rejudgment simple code like the one you posted was AC, but not anymore
Those Who Don't Know History are doomed to repeat it
samuelcdf
New poster
Posts: 3
Joined: Tue Dec 04, 2001 2:00 am
Contact:

please help me to point out my code wrong. I try much times, but still can find the error ><~~

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

void main(void)
{
unsigned long i=0L, input_i=0L, j=0L, max=0L;
unsigned long counter=0L, temp=0L;

while(scanf("%lu %lu", &i, &j)==2)
{
if(i>j)
{
temp=i;
i=j;
j=temp;
}
for(input_i=i;i<=j;i++)
{
temp=i;
counter=1L;
while(temp!=1)
{
if(temp%2==0)
{
temp/=2;
}
else
{
temp=(3*temp)+1;
}
counter++;
}
if(counter>max)
max=counter;
}
printf("%lu %lu %lu\n", input_i, j, max);
max=0;
}
}

``````
Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
when i>j you swap i,j but in the output you should print the i,j pair in the original order as in input
samuelcdf
New poster
Posts: 3
Joined: Tue Dec 04, 2001 2:00 am
Contact:

### picard thank you very much!!!

Thank you very much!!!
My head is big, but I am stupid...... haha~~~ ^^a
eureka
New poster
Posts: 5
Joined: Sun Sep 15, 2002 11:15 am

### help p100

why my code is compile error.
who can help me

#include <stdio.h>
#include <math.h>

int main()
{

long n[10001];

long i,j;

long count,len,a ;

for (long p = 1;p<=10000;p++)
{

n[p] = 1;
len = 1;
a = p;

while (a!=1)
{

if (fmod(a,2) == 1)

a = 3*a + 1 ;

else

a = a/2;

len++;

}

n[p] = len;

}

while (scanf("%ld %ld",&i,&j) == 2)

{
count = n;

for (int k = i;k<=j;k++)
{
if (n[k] > count)
count = n[k];
}
printf("%ld %ld %ld\n",i,j,count);

}
return 0;

}
zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### (a) few thoughts

First are you sure you send it az C++, not as a C code.
Second this variable count. I am not sure but if it is doubled in the compiler as a reserved word there may be trouble.
And last, but not least It would be great if pasted and the errors the jusge returned to you. See, normally(if option not switched off) it will send you a letter with subject "Compile error". In its body there will be written the rrors occured during compilation.
If you still have problems post back the errors.
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com