100 - The 3n + 1 problem

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

Moderator: Board moderators

popinc
New poster
Posts: 2
Joined: Thu Nov 23, 2006 11:18 pm

Post by popinc » Wed Nov 29, 2006 2:03 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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Thu Nov 30, 2006 1:12 pm

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
form kisui na ... class tai asol....
iF U hv d class u get the form....

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

Post by emotional blind » Thu Nov 30, 2006 10:19 pm

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

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

Post by joy » Fri Dec 01, 2006 6:23 pm

Thanks, I got 0.066 now :) ,
but how can anyone solve it 0.000 or 0.002 :roll: ?
form kisui na ... class tai asol....
iF U hv d class u get the form....

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

Post by emotional blind » Sat Dec 02, 2006 7:29 pm

what about other parts of your programm.. ?

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

Post by joy » Sat Dec 02, 2006 7:48 pm

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);
	}
}
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

Post by tanvm » Mon Dec 04, 2006 7:34 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{
    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
New poster
Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm

Post by mhulboj » Sun Dec 10, 2006 8:00 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

Post by tan_Yui » Mon Dec 11, 2006 2:30 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

Post by kirangonella » Wed Dec 20, 2006 5:10 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Dec 20, 2006 5:52 pm

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

User avatar
Debashis Maitra
Learning poster
Posts: 62
Joined: Sun Jul 09, 2006 8:31 am
Location: University of Dhaka
Contact:

Post by Debashis Maitra » Mon Dec 25, 2006 8:48 pm

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
Akash chhoyar swopno
Dream to touch the sky

Mistico
New poster
Posts: 1
Joined: Sun Jan 07, 2007 9:59 pm

Post by Mistico » Sun Jan 07, 2007 10:06 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

Post by code_man » Thu Feb 01, 2007 11:08 am

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;
}

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Fri Feb 02, 2007 11:18 am


Post Reply

Return to “Volume 1 (100-199)”