## 100 - The 3n + 1 problem

Moderator: Board moderators

popinc
New poster
Posts: 2
Joined: Thu Nov 23, 2006 11:18 pm
Caching the cycle length of small values, e.g. 1~100000 makes a lot sense, however, I found that even though the cycle length are cached, the runtime is still more than 50ms, among which 20ms was used to build the cache.

Any idea to further improve the runtime performance? Thanks a lot!

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
I solved it with CPU: 0.088 and minimum memory.
Using this function:

Code: Select all

``````int func(long long n)
{
int r;
if(n<=1000000 && a[n])
return a[n];
if(n%2==0)
r=1+func(n/2);
else
r=1+func((n*3+1));
if(n<=1000000)
a[n]=r;
return r;
}``````
How I improve my timing??
form kisui na ... class tai asol....
iF U hv d class u get the form....

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Instead of long long just use int and give us report.

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
Thanks, I got 0.066 now ,
but how can anyone solve it 0.000 or 0.002 ?
form kisui na ... class tai asol....
iF U hv d class u get the form....

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:

Code: Select all

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

short int a;
int func(int n)
{
//	printf("%I64d ", n);
int r;
if(n<=1000000)
if(a[n])
return a[n];
if(n%2==0)
r=1+func(n/2);
else
r=1+func((n*3+1));
if(n<=1000000)
a[n]=r;
return r;
}

int find(int i, int j)
{
int max=0;
int i1;
for(i1=i; i1<=j; i1++)
{
if(a[i1]==0)
a[i1]=func(i1);
if(max<a[i1])
max=a[i1];
}
return max;
}

void main()
{
int i, j, res;

a=1;
while(scanf("%d %d",&i, &j)==2)
{
printf("%d %d ", i, j);
if(i>j)
res=find(j, i);
else
res=find(i, j);
printf("%d\n",res);
}
}``````
form kisui na ... class tai asol....
iF U hv d class u get the form....

tanvm
New poster
Posts: 1
Joined: Mon Dec 04, 2006 7:30 pm
Hi, I am a new comer.
I have read many threads on this problem but I still cannot figure out why my submission is still WA.

Code: Select all

``````/*
* Main.java
*  java program model for www.programming-challenges.com
*/

import java.io.*;
import java.util.*;

class Main implements Runnable{
byte line[] = new byte [maxLength];
int length = 0;
int input = -1;
try{
while (length < maxLength){//Read untill maxlength
if ((input < 0) || (input == '\n')) break;
line [length++] += input;
}

if ((input < 0) && (length == 0)) return null;  // eof
return new String(line, 0, length);
}catch (IOException e){
return null;
}
}

public static void main(String args[])  // entry point from OS
{
Main  myWork = new Main();
myWork.run();            // execute
}

public void run() {
new myStuff().run();
}
}
class myStuff implements Runnable{
private char[][] arr;
public void run(){

String str;
if(str.length()==0) break;
int loc=str.indexOf(" ");
//System.out.println(str);
int num1=Integer.parseInt(str.substring(0, loc));
int num2 = Integer.parseInt(str.substring(loc+1));
int max=0;
boolean b=true;
if(num1>num2){
b=false;
int tmp=num1;
num1=num2;
num2=tmp;
}
for (int j=num1;j<=num2;j++){
int count=1;
int i=j;
while(i>1){
if((i%2)==0) i/=2;
else i=3*i+1;
count++;
}

max=Math.max(max,count);
}
if(b) System.out.println(num1+" "+num2+" "+max);
else System.out.println(num2+" "+num1+" "+max);
}

}
// You can insert more classes here if you want.
}
``````

mhulboj
New poster
Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm
Could someone provide a hint why this code yields WA?

Code: Select all

``````...
``````
Resolved, thx.
Last edited by mhulboj on Mon Dec 11, 2006 9:28 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
mhulboj wrote:Could someone provide a hint why this code yields WA?
If "2 3" was inputted, output should be "2 3 8". By the way, you should remove your JUDGE_ID from your previous post by editing,
because there is danger to which your ID is misused by the third party.

Best regards.

kirangonella
New poster
Posts: 1
Joined: Wed Dec 20, 2006 3:55 pm

### can anyone help me out in finding the error in it..its 3n+1

here is my code:

/* 3n+1 problem */
#include<stdio.h>

int processing(int);
main()
{
int a,i,j,k,max=1;

for(i=0;i<4;i++)
{
for(j=0;j<2;j++)
{
scanf("%d",&a[j]);
}
}
for(i=0;i<4;i++)
{
max=1;
for(j=a;j<=a;j++)
{
k= processing(j);
if(k>max)
max=k;
}
printf("%d %d %d\n",a,a,(max+1));
}

return 1;
}
int processing(int j)
{
long int m;
int n;
m=(long int)j;
n=0;
for(;m>1;)
{
if(m%2!=0)
{
m=(3*m)+1;
n++;
}
else if(m%2==0)
{
m=m/2;
n++;
}
}
return n;
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You're not supposed to make a new thread on this problem..
Check this out..
http://online-judge.uva.es/board/viewtopic.php?t=3015

Debashis Maitra
Learning poster
Posts: 62
Joined: Sun Jul 09, 2006 8:31 am
Location: University of Dhaka
Contact:
I think its your first post
so next time be care full to open a new thread

ok

i have solved this problem long days ago

i used long in printing part also

remember u shouldn't open new thread if another thread is available on that topic

and post ur code using "code tag" it helps another person to view your code

Finally remove your code after AC

Best of luck
Akash chhoyar swopno
Dream to touch the sky

Mistico
New poster
Posts: 1
Joined: Sun Jan 07, 2007 9:59 pm
I cannot find the error in this code, but I always get a WA error.. can anyone help me plz?

Code: Select all

``````Resolved, thanks!
``````

code_man
New poster
Posts: 4
Joined: Tue Jan 16, 2007 6:07 pm

### 100

I don't understand this check system.. Yesterday I submit this code and answer was WA but tuday I send this same code and was AC?? is it strange??

#include <iostream>

using namespace std;

int main(void){
long i,j,m,temp,total,max;
while(cin>>i>>j){
cout<<i<<" "<<j<<" ";
max=0;
if(i>j){
temp=i;
i=j;
j=temp;
}
for(m=i;m<=j;m++){
temp=m;
total=0;
while(1){
if(temp==1){
total++;
break;
}
total++;
if(temp%2==0) temp/=2;
else temp=3*temp+1;
}
if(total>max) max=total;
}
cout<<max<<endl;
}
return 0;
}

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm
http://online-judge.uva.es/board/viewtopic.php?t=3015   