100 - The 3n + 1 problem

[Codemonkey2000]

This problem is really tuff, even if it is the first one, anyway here is a source code, it got AC.

var
i, j: integer;

function getCL(N: integer): integer;
var k: integer;
begin
k := 1;
while N <> 1 do begin
if odd(N) then N := 3*N + 1
else N := N div 2;
k := k + 1;
end;
getCL := k;
end;

function getMaxCL(i, j: integer): integer;
var k: integer;
max, curCL: integer;
begin
max := 0;
for k:=i to j do begin
curCL := getCL(k);
if curCL > max then max := curCL;
end;
getMaxCL := max;
end;

begin
while not eof(input) do begin
readln(i, j);
write(i, ' ', j, ' ');
if i < j then
writeln(getMaxCL(i, j))
else
writeln(getMaxCL(j, i));
end;
end.

Sorry about quoting an old post, but I tried this code, and it also gives me Time Limit exceeded. Is the pascal compiler working properly?

[Codemonkey2000]

Code: Select all

#include<iostream>

int foo(long num)
{
	long c=num;
	long iter=1;
	while (c!=1)
	{
		if ((c%2)==0)
			c/=2;
		else
			c=c*3+1;
		iter++;
	}
	return iter;
}

int main()
{
	long i,j,tmp,max;
	while (std::cin>>i>>j)
	{
		std::cout<<i<<" "<<j<<" ";
		if (i>j)
		{
			tmp=i;
			i=j;
			j=tmp;
		}
		max=0;
		for (long x =i;x<=j;x++)
		{
			tmp=foo(x);
			if (tmp>max)
				max=tmp;
		}
		std::cout<<max<<std::endl;
	}
}

There is something definitely wrong with the pascal compiler. I translated the code from pascal into c++ and got AC.

[blackfire]

Plz Help with my java code

Code: Select all

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

class Main
{
	Arbol tree;
	int cont;
	int de;
	public static void main(String args[])
	{
		Main myWork = new Main();
		myWork.Begin();
	}
	public int teur(long n)
	{
		int temp = tree.buscar(n);
		//System.out.println(n);
		if(n==1)
			return 1;
		else
		{
			if(temp==0)
			{	
				cont ++;
				temp = 1 + teur(((n%2)==0)?n/2:(3*n+1));
				tree.insertaNodo(n, temp);
			}
			de++;
		}
		return temp;
	}
	public void Begin()
	{
		String input;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		tree = new Arbol();
		cont = 0;
		de = 0;
		int a, b, min, max, mayor, c;
		try{
			while((input = in.readLine())!=null)
			{
				a = Integer.parseInt(input.split(" ")[0]);
				b = Integer.parseInt(input.split(" ")[1]);
				if(a < b ){ min = a; max = b;}else{min = b; max = a;}
				mayor=-1;
				for(long n = min; n<=max; n++)
				{
					c = teur(n);
					if(c>mayor) mayor = c;
				}
				out.println(a + " " + b + " " + mayor);
				out.flush();
			}
		}catch(Exception ex){System.exit(0);}
	}
	class Arbol
	{
		Nodo raiz;
		public Arbol()
		{
			raiz = null;
		}
		public void insertaNodo(long d, int c)
		{
			if(raiz==null)
			{
				raiz = new Nodo(d, c);
			}else{
				Nodo aux = new Nodo(d, c);
				Nodo actual = raiz;
				if((d%2)==0)
				{
					if(actual.getRight()==null)
						actual.setRight(aux);
					}else{
					if(actual.getLeft()==null)
						actual.setLeft(aux);
					else
						insertaHijo(actual.getLeft(),aux);
				}
			}
		}
		public void insertaHijo(Nodo rama,Nodo aux)
		{
			while(rama!=null)
			{
				if(rama.getData()<aux.getData())
				{
					if(rama.getLeft()!=null)
					{
						rama = rama.getLeft();
					}else{
						rama.setLeft(aux);
						return;
					}
				}else{
					if(rama.getRight()!=null)
					{
						rama = rama.getRight();
					}else{
						rama.setRight(aux);
						return;
					}
				}
			}
		}
		public int buscar(long d)
		{
			if(raiz==null)
				return 0;
			else
			{
				Nodo actual = raiz;
				if(raiz.getData()==d)
					return raiz.getCount();
				else
				{
					if((d%2)==0)
					{
						return busquedaR(raiz.getRight(),d);
					}else{
						return busquedaR(raiz.getLeft(),d);
					}
					
				}
			}
		}
		public int busquedaR(Nodo rama, long d)
		{
			
			while(rama!=null)
			{
				if(rama.getData()==d)
				{
					return rama.getCount();
				}else{
					if(rama.getData()<d)
					{
						rama = rama.getLeft();
					}else{
						rama = rama.getRight();
					}
				}
			}
			return 0;
		}
	}
	class Nodo
	{
		long dato;
		int count;
		Nodo izq;
		Nodo der;
		public Nodo(long d, int c)
		{
			dato = d;
			count = c;
			izq = null;
			der = null;
		}
		
		public long getData()
		{
			return dato;
		}
		public int getCount()
		{
			return count;
		}
		public Nodo getLeft()
		{
			return izq;
		}
		public Nodo getRight()
		{
			return der;
		}
		public void setLeft(Nodo n)
		{
			izq = n;
		}
		public void setRight(Nodo n)
		{
			der = n;
		}
	}
}

I get WA error for a month

[bogertron]

I really hope that this is not a logic problem, but I am trying to enter a solution to problem 100 and I am getting a RunTime error
Here is the code:

Code: Select all

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

public class Main {

    public static String sequenceEvaluator(int begin, int end){
        return (begin + " " + end+ " " + sequenceEvaluatorHelper(begin, end));
    }

    private static int sequenceEvaluatorHelper(int begin, int end){
        int maxTimes = -1;
        int timesThroughCycle;
        int start;
        if(end < begin){
            start = begin;
            begin = end;
            end = start;
        }
        for(int dummy = begin; dummy <= end; dummy++){
            timesThroughCycle = 1;
            start = dummy;
            while(start != 1){
                if(start % 2 == 1){
                    start = 3*start+1;
                }else{
                    start = start/2;
                }
                timesThroughCycle++;
            }
           // System.out.println("Times through: " + timesThroughCycle);
            if(timesThroughCycle > maxTimes){
                maxTimes = timesThroughCycle;
            }
        }
        return maxTimes;
    }


    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
         while(in.hasNext()){
                String[] numbers = in.nextLine().split(" ");
                int start = Integer.parseInt(numbers[0]);
                int end = Integer.parseInt(numbers[1]);
                System.out.println(sequenceEvaluator(start, end));
        }
    }

}

Thanks in advance[/code]

[mf]

Input numbers may be separated by two or more spaces, and there could be leading and trailing spaces on lines.

in.nextLine().split(" ") returns not what you expect in these cases.

[knascj]

Help!
I received a runtime error

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

int main()
{
int i,j,a[100],b[100],c[100];
int aux,cont=0,n,p,cl,max_cl=0;//cl-cycle lenght
while (scanf("%d %d",&i,&j)!=EOF)
{
if(i>j)
{
aux=i;
i=j;
j=aux;
aux=1;
}

for(n=i;n<=j;n++)
{
cl=1;p=n;
while(p>1)
{
if(p%2==0)p=p/2;
else p=3*p+1;
cl++;
}

if(max_cl<cl)max_cl=cl;

}

if(aux==1)
{
aux=i;
i=j;
j=aux;
}

a[cont]=i;
b[cont]=j;
c[cont]=max_cl;
cont++;


}

for(n=0;n<cont;n++)
printf("%d %d %d\n",a[n],b[n],c[n]);

system("pause");
}

[dustfinger]

Submission number: #6245490
Language: c++
browser: firefox

I keep getting WA for my result. Actually, once I submit to the judge I end up back at the problem page, but when I goto my submissions then I see that the verdict was "Wrong Answer". Is that how it is suppose to work? My time is always 0.000. I programmed it so that it would accept any number of arguments as long as 1 == argc %2 since the first argument is the program name. So here is an example run on my own system.

Code: Select all

./a.out 10 1 100 200 201 210 900 1000
10 1 20
100 200 125
201 210 89
900 1000 174

What I find surprising is that my code finishes in 0 time. It seems to be outputting correct results, so if they had some case that I had not considered I would still think that my program would last longer than 0 time. This makes me wonder if something else is wrong. I can submit my code if anyone is interested in helping me. Is it proper etiquette to fill the thread with ones code?

Sincerely,

dustfinger

[mf]

You should take input from stdin.

i.e. it should work with

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out

[dustfinger]

mf,

You are correct! I made the appropriate change so that my code now reads from standard input and I got the Accepted verdict with a runtime of 0.720

Sincerely,

dustfinger

[dustfinger]

knascj,

I compiled your code and ran it with the following input:

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out
10 1 20
200 100 125
201 210 125
900 1000 174
sh: pause: command not found

I then I removed the System call

Code: Select all

system("pause");

and I ran the code again:

Code: Select all

echo 10 1 100 200 201 210 900 1000  | ./a.out
10 1 20
200 100 125
201 210 125
900 1000 174

I compiled your code using gcc version 4.1.2 (Gentoo 4.1.2 p1.0.2)

dustfinger.

[karthikeyan1171]

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!!

[CSEDU_1323]

hi,

use return 0; instead return 1;

&&

sample input

10 20
20 10

sample output

10 20 21
20 10 21

HOPE THIS HELPS

[karthikeyan1171]

Hi,
It works, The problem was that when I was printing the output if the inputs are 20 10, I print it as 10 20 in the wrong order. I don't know how does it matter.. but anyway it has accepted the solution.

-- Thanks

[hszeeks]

hi, i am newbie..
I've just in this forum and also just a few days joining online judges, and the only language i can is pascal..
anybody plis can help me solving the 100 problem using pascal?
i just don't understand c, c++, and i don't even understand the problem..
am i wrong defining the problem in this way:
look for the maximum cycle length between two integer from the input..
maximum cycle length: number printed as output from the algorithm given as the problem

i tried this code:

uses crt;

var a:integer;

begin
clrscr;
write('Input: ');readln(a);
if a=1 then exit;
write(a, ' ');
while a>1 do begin
if a mod 2 = 1 then begin a:=a*3+1;write(a, ' ');end;
if a mod 2 = 0 then begin a:=a div 2;write(a, ' ');end;
end;
readln;
end.

i just wrote the algorithm, input 22, and the output is the same as in the problem, now i just need to write codes to count it, and then apply it to the input (numbers between 2 integer) isn't it?
i am really confused and not knowing what to do know..
anybody can help me by subscribing the code maybe?

[mf]

There's a sample Pascal solution to this problem on the site - http://online-judge.uva.es/problemset/data/p100.p.html