100 - The 3n + 1 problem

[chien_chien]

Code: Select all

#include <iostream>

using namespace std;

#define MAX 1000000    // max int for input

// cycle_length_array[i] store the value of int i, init value is 0
int cycle_length_array[MAX];  
int generate_cycle_length(int n);  
int get_max_cycle_length(int start, int end);

int main()
{
	int start = 0;
	int end = 0;
	int max = 0;
	while (cin>>start>>end)
	{
		if (start > end)
		{
			max = get_max_cycle_length(end, start);
		}
		else
		{
			max = get_max_cycle_length(start, end);
		}
		cout << start << " "<< end << " "<< max<<endl;
	}
	return 1;
}

int generate_cycle_length(int n)
{
	int count = 1;
	while (n != 1)
	{
		if (n % 2)
		{
			n = 3 * n + 1;
		}
		else
		{
			n /= 2;
		}
		count += 1;
	}
	return count;
}

int get_max_cycle_length(int start, int end)
{
	int max = 0;
	for (int i = start; i <= end; ++i)
	{
		if (cycle_length_array[i] == 0)
		{
			cycle_length_array[i] = generate_cycle_length(i);
		}
		if (cycle_length_array[i] > max)
		{
			max = cycle_length_array[i];
		}
	}
	return max;
}

runtime : 0.100 secs

have any one get runtime : 0.008

[khepani]

Hello, can somebody tell me why I am getting wrong answer? These are both optimized and brute force codes:

Optimized:
import java.io.*;
import java.util.*;
public class Main{
static long maxSteps=1;
static long[]bigMatrix=new long[1000001];
static StringTokenizer st;
static int veces=0;
public static void main(String[]args)throws IOException{
Scanner scanner=new Scanner(System.in);
for(int i=0;i<1000001;i++) bigMatrix=1;
st=new StringTokenizer(scanner.nextLine());
while(st.hasMoreTokens()){
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
for(int i=Math.min(a,b);i<=Math.max(a,b);i++){
long nTemp=calcula(i);
if(nTemp>maxSteps) maxSteps=nTemp;
}
if(veces==0) System.out.print(Math.min(a, b)+" "+Math.max(a, b)+" "+maxSteps);
else System.out.print("\n"+a+" "+b+" "+maxSteps);
maxSteps=1;
st=new StringTokenizer(scanner.nextLine());
}
}

public static long calcula(int number){
long count=1;
int initial=number;
while(number!=1){
if(bigMatrix[initial-1]>1){
count=bigMatrix[initial-1];
break;
} else{
if(number%2==0) number/=2;
else number=3*number + 1;
count++;
}
if(number==1) bigMatrix[initial-1]=count;
}
return count;
}
}


Not Optimized (just change one method):

public static long calcula(int number){
long count=1;
int initial=number;
while(number!=1){
if(number%2==0) number/=2;
else number=3*number + 1;
count++;
}
return count;
}

[khepani]

Hello, can somebody tell me why I am getting wrong answer? These are both optimized and brute force codes:

Optimized:
import java.io.*;
import java.util.*;
public class Main{
static long maxSteps=1;
static long[]bigMatrix=new long[1000001];
static StringTokenizer st;
static int veces=0;
public static void main(String[]args)throws IOException{
Scanner scanner=new Scanner(System.in);
for(int i=0;i<1000001;i++) bigMatrix=1;
st=new StringTokenizer(scanner.nextLine());
while(st.hasMoreTokens()){
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
for(int i=Math.min(a,b);i<=Math.max(a,b);i++){
long nTemp=calcula(i);
if(nTemp>maxSteps) maxSteps=nTemp;
}
if(veces==0) System.out.print(Math.min(a, b)+" "+Math.max(a, b)+" "+maxSteps);
else System.out.print("\n"+a+" "+b+" "+maxSteps);
maxSteps=1;
st=new StringTokenizer(scanner.nextLine());
}
}

public static long calcula(int number){
long count=1;
int initial=number;
while(number!=1){
if(bigMatrix[initial-1]>1){
count=bigMatrix[initial-1];
break;
} else{
if(number%2==0) number/=2;
else number=3*number + 1;
count++;
}
if(number==1) bigMatrix[initial-1]=count;
}
return count;
}
}


Not Optimized (just change one method):

public static long calcula(int number){
long count=1;
while(number!=1){
if(number%2==0) number/=2;
else number=3*number + 1;
count++;
}
return count;
}

[khepani]

I changed this

Code: Select all

if(veces==0) System.out.print(Math.min(a, b)+" "+Math.max(a, b)+" "+maxSteps);
else System.out.print("\n"+a+" "+b+" "+maxSteps);

for this:

if(veces>0)
System.out.println();
System.out.print(Math.min(a, b)+" "+Math.max(a, b)+" "+maxSteps);
veces=1;

Still not working

[khepani]

Solved xD I tought I shouldn't end with a '\n'

[aaa111]

Hi,I am new here.Why i am getting RUNTIME ERROR for my code:

Code: Select all

#include<stdio.h>

int main()
{
unsigned int m,n,x[20],y[20],i,j,c,mc[20],k,size,t;

i=0;
j=0;

while(scanf("%lu %lu",&x[i],&y[i])==2)	
	{
	if(x[i]>y[i])
		{
		t=x[i];
		x[i]=y[i];
		y[i]=t;
		}
	mc[i]=0;
	i++;	
	}

c=0;
mc[0]=1;

for(j=0;j<i;j++)
{
for(m=x[j];m<y[j];m++)
{
n=m;

while(n>=1)
{
c++;
if(n==1)
	{
	break;
	}

if((n%2)!=0)
	n=(3*n)+1;
else
	n=n/2;
}
if(mc[j]<c)
	mc[j]=c;
c=0;
}

}

for(j=0;j<i;j++)
	printf("%lu %lu %lu\n",x[j],y[j],mc[j]);

return 0;
}

[kareemergawy]

I didn't want to post this but I am getting disappointed
I sent this Java solution but it keeps sending me an RE (This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.)

Code: Select all

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Problem;

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

/**
 *
 * @author Kareem Ergawy
 */
class Main {

    public static final int SIZE = 100001;
    private int[] cycleLenght = new int[SIZE];

    static String ReadLn(int maxLength) {  // utility function to read from stdin,
        // Provided by Programming-challenges, edit for style only
        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; //or untill end of line ninput
                }
                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();  // Construct the bootloader
        myWork.run();            // execute
        System.exit(0);
    }

    public void run() {
        cycleLenght[1] = 1;
        String nextLine = null;

        while (!(nextLine = Main.ReadLn(Byte.MAX_VALUE)).equals("")) {
            Scanner scanner = new Scanner(nextLine);
            int i = scanner.nextInt();
            int j = scanner.nextInt();
            int maxCycle = 0;

            if (i < j) {
                for (int x = i; x <= j; x++) {
                    int tmp = calcCycleLength(x);

                    if (maxCycle < tmp) {
                        maxCycle = tmp;
                    }
                }
            } else {
                for (int x = j; x <= i; x++) {
                    int tmp = calcCycleLength(x);

                    if (maxCycle < tmp) {
                        maxCycle = tmp;
                    }
                }
            }

            System.out.println(i + " " + j + " " + maxCycle);
        }
    }

    public int calcCycleLength(int n) {
        if (n < SIZE && cycleLenght[n] != 0) {
            return cycleLenght[n];
        }

        if (n % 2 == 0) {
            if (n < SIZE) {
                cycleLenght[n] = 1 + calcCycleLength(n >> 1);
                return cycleLenght[n];
            } else {
                return (1 + calcCycleLength(n >> 1));
            }
        } else {
            if (n < SIZE) {
                //http://loblog.wordpress.com/2007/03/29/programming-challenge-the-3n1-problem/
                cycleLenght[n] = 2 + calcCycleLength((3 * n + 1) >> 1);
                return cycleLenght[n];
            } else {
                return 2 + calcCycleLength((3 * n + 1) >> 2);
            }
        }
    }
}

Any hints on how to even get to a WA

[aaa111]

Finally got accepted.

[slimmz]

Hi!
I'm getting WA always if I use recursive iteration...
Can someone tell me, what's going on? I wrote an iterative method instead and the problem got accepted.
However I compared the output of those two different approaches and the output was identical (iterated 1 ... 999999).

Here is my code with recursice method (algo):

Code: Select all

#include <iostream>
using namespace std;

long algo(long,long);
long find(long,long);

long algo(long a, long cnt){
  if(a==1){
    return cnt+1;
  }else{
    if(a%2!=0){
      algo((3*a)+1,cnt+1);
    }else{
      algo(a/2,cnt+1);
    }
  }
}

long find(long a,long b){
  long tmp = 0;
  long max = 0;
  for(; a<=b; a++){
    tmp = algo(a,0);
    if(max<=tmp)max=tmp;
  }
  return max;

}

int main(){
    char input_line[100];
    int a,b;

    while(cin.getline(input_line,100)) {
      sscanf(input_line, "%d %d",&a,&b);
      if(a<=b){
        printf("%d %d %d\n",a,b,find(a,b));
      }else{
        printf("%d %d %d\n",a,b,find(b,a));
      }
    }
  return 0;
}

[mintae71]

Thanx you to your advice~~~

[mintae71]

Please tell me, anything wrong with this code.

/* 3n+1 problem */
#include<stdio.h>
int main()
{
unsigned long i,j,m,n,temp; /* i and j used to store the inputs,m and n is used in for loops */
unsigned long cycles = 1; /* To store no of cycles , initialized to 1 so that it includes last one*/
unsigned long max = 0; /* To store max no of cycles scanned */

do
{
scanf("%li",&i);
if(feof(stdin)) break;
scanf("%li",&j);
if(feof(stdin)) break;

if(i>j)
{
temp=i;i=j;j=temp;
}
for(m=i; m<=j ; m++)
{
n = m;
cycles = 1;
while(n != 1)
{
if(n&1)
n=3*n+1;
else
n/=2;

cycles ++;
}
if(cycles > max)
max = cycles;
}
printf("%li %li %li\n", i,j,max);
max = 0;
}while(!feof(stdin));
return 1;
}


Thanks!!

I think you had a mistake.....
Why did't you checked when i < j or i == j?

[hmaciel]

Hey, Im having some problems with this problem, Ive tried all the possible inputs and I get a right output but the judge keeps saying wrong answer. Could anybody put an eye on it and tell me if Im doing something wrong?

Heres my code.

Thanks in advanced.

Code: Select all

#include <iostream>
#include <stdio.h>

using namespace std;

int np(unsigned int num, unsigned int res){
	if (num == 1){
		return res;
	}else{ 
		if (num%2 != 0){
			res++;
			np((3*num)+1,res);
		}else{
			res++;
			np(num/2,res);
		}
	}
}

int main ()
{
   int a,b,max,temp;
      while(scanf("%d %d", &a,&b) != EOF){
      max = 0;
      printf("%d %d",a,b);
      if(a>b){ 
	swap(a,b);
      }
      for(a;a<=b;a++){
	 temp = np(a,1);
	 if(max < temp)
	    max = temp;
      }
      printf(" %d\n", max);
      }
  return 0;
}

[mf]

Not all control paths in your np() function return a value. Unlike some other languages (like Lisp, where functions return value of last statement), in C/C++ you must explicitly use a "return <expression>;" statement to return some value from a function. If control exits a function but not through a return statement, some garbage will likely be returned to the caller.

Your compiler should've warned you about that.

And it's safer to check that scanf("%d %d", &a,&b) == 2 instead of EOF.

[hmaciel]

Thank you, i didnt realize about the return statemets, i got it accepted!

[hmaciel]

Youre missing the same thing that I missed. the algo function must return something on each statment instead of just calling algo(.....) on the if statment you have to do return (algo (......));. and itll work.