100 - The 3n + 1 problem

[popinc]

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]

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??
Please help

[emotional blind]

Instead of long long just use int and give us report.

[joy]

Thanks, I got 0.066 now ,
but how can anyone solve it 0.000 or 0.002 ?

[emotional blind]

what about other parts of your programm.. ?

[joy]

Code: Select all

#include<stdio.h>

short int a[1000005];
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]=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);
	}
}

[tanvm]

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{
    static String ReadLn(int maxLength){  
        byte line[] = new byte [maxLength];
        int length = 0;
        int input = -1;
        try{
            while (length < maxLength){//Read untill maxlength
                input = System.in.read();
                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(){
        
        // Your program here
            String str;
            while((str=Main.ReadLn(255))!=null){
                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.
}

Thanks in advance.

[mhulboj]

Could someone provide a hint why this code yields WA?

Code: Select all

...

Resolved, thx.

[tan_Yui]

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]

here is my code:

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

int processing(int);
main()
{
int a[4][2],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[0];j<=a[1];j++)
{
k= processing(j);
if(k>max)
max=k;
}
printf("%d %d %d\n",a[0],a[1],(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]

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]

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

u can try it. This may help you

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

[Mistico]

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]

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]

http://online-judge.uva.es/board/viewtopic.php?t=3015