100 - The 3n + 1 problem

[Insidetheasylum]

Ah! Great =D

Now I gotta go and fix it so that it falls directly under the scope of the rules since I think the program doesn't accept command line instructions =/

[Larry]

Read through all the common mistakes on this thread.. you make one of them..

[nicu_ivan]

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.

[_davidf]

Sorry, I didn't see the sticky.

[59446TY]

I have gotten problem 100 to (accepted) in both Java an C, and I believe there to be a problem with the judge. The C program works no problem, but initially the Java program did not. I added a "hack" to the Java program, which actually causes it to miscalculate some values, and this program was accepted as correct.

The problem is that, in C even an unsigned long is not large enough to handle some of the numbers that will be encountered during calculation of the 3n+1 series. These numbers are (incorrectly) truncated, thus making 3n+1 < n sometimes. This doesn't cause any problems, assuming that I write my program in C, and the judge solutions are done in C, as they make the same mistakes and get matching answers.

However, if you use Java, it doesn't have the same limit for its long integers. It correctly calculates different values, thus not matching the (incorrect) judge. If you add in a hack into your java code, that is to truncate any value over the LONG_MAX value of c, you can get the java program to be accepted.

Just thought you might want to know that your "accepted" programs are all flawed, and perhaps it will help some students to be less frustrated with non-working java submissions.

[wintersoul]

i got WA for my code.. and i cant figure why..

someone please help me look at my code and tell me what's wrong with it

Code: Select all

#include <iostream>

using namespace std;


int calcyclength(int);
int x, cltemp;

void main()
{
  int i,in;
  int j,jn;

  int cyclelength=1;
  int counter;

  while (cin >> i >> j)
  {
	
    cyclelength=1;  
    
    if (i > j)
	{
		in = j;
		jn = i;
	}
	else 
	{
		in = i;
		jn = j;
	}

	for (x = in; x <= jn; x++)
	{
		counter = calcyclength(x);

		if (cyclelength < counter)
			cyclelength = counter;
		cltemp = counter -1;
		counter = 1;
		
	}

    cout << i << " "<< j << " " << cyclelength << endl;
  }
  
}

int calcyclength(int a)
{
	int counter=1;
	while (a != 1)
	{
		if (a % 2 == 0)
		{
			a = a / 2;
		}
		else 
		{								
			a = 3 * a + 1;
		}
			
		counter++;
		if (a==x-1)
		{
			counter= counter + cltemp;
			break;
		}

	}
	
	
	return counter;
}

[Grazyna]

I submited the following code with Submit-o-matic and I got wrong answer. I read all the posts concerned problem 100 and I can not understand my mistake(s). Thanks in advance for any help.

Code: Select all

/* @JUDGE_ID:  xxxxxxxx  100  C++   */

#include <iostream>

using namespace std ;

unsigned long xPlusOne(unsigned long n) ; 


unsigned long orbit(unsigned long n) ;


unsigned long maxOrbit(unsigned long n , unsigned long m) ;


int main(){
unsigned long i , j ;
while(cin >> i >> j) {
	cout << i << ' ' << j << ' ' ;
	if (i>j) cout << maxOrbit(j,i) ;
	else cout << maxOrbit(i,j) << endl ; }	
return 0;}


unsigned long xPlusOne(unsigned long n){
	if (n%2)  return 3*n+1 ; 
	else return n/2 ;}

unsigned long orbit(unsigned long n){
unsigned long count=1 ;
unsigned long hold = n ;
while(hold != 1) {
	hold = xPlusOne( hold ) ;
	++count;}
return count ;}


unsigned long maxOrbit(unsigned long n , unsigned long m){
	unsigned long count ;
	unsigned long max=1 , hold ;
	for(count=n;count<=m;++count)
		{ hold =  orbit(count) ;
		if (hold > max) max = hold ;}
	return max ; }

[jakabjr]

I think tour error is in

Code: Select all

   if (i>j) cout << maxOrbit(j,i) ; 

you are missing an "<< endl", thus you print two numbers concateneted (that's why it's not P.E.)

[Grazyna]

Thanks jakabjr. I just started to learn C++ and I was afraid that there was some deep language problem.

[ppponline]

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

class Main {
public static void main(String[] args) {
int i;
int j;
while(true){
String s=getLine();
StringTokenizer parser=new StringTokenizer(s);
if((parser.countTokens())!=2){
break;
}
else{
i=Integer.parseInt(parser.nextToken());
j=Integer.parseInt(parser.nextToken());
solve(i,j);
}
}
}
static void solve(int p,int q){
int n;
int c;
int k;
int max=0;
for(k=p;k<=q;k++){
n=k;
int count=1;
while(n!=1){
count++;
if((c=n%2)==1){
n=3*n+1;
}
else
n=n/2;
}
if(count>max){
max=count;
}
}
System.out.println(p+" "+q+" "+max);
}


public static String getLine(){
StringBuffer buf=new StringBuffer(80);
int c;
try{
while((c=System.in.read())!=-1){
char ch=(char) c;
if(ch=='\n')
break;
buf.append(ch);
}
}catch (IOException e){
System.err.println(e);
}
return (buf.toString());
}
}


==============================================

I don't know where the bug is.
Who can tell me ... thx.

[chunyi81]

Please see the sticky thread in this forum on problem 100. You are making the same mistake stated there. You did not handle the case i > j
Please browse through the forum for posts related to your problem before posting in future.

[Ivchencov]

include <iostream>


using namespace std;
void main()
{
long i,g,j,k,n1, max,tmp,tmp1;
while (cin >> i >>j)
{
if (j<i)
{
tmp1=i;
i=j;
j=tmp1;
cout << j << " " << i;
}
else
cout << i << " " << j;
tmp=0;
for (k=i;k<=j; k++)
{
max=1;

n1=k;
while (n1!=1)
{
if (n1 % 2 == 0){
n1 = n1/2;
}
else{
n1 = 3*n1+1; }
max++;
if (max>tmp)
{
tmp=max;
}


}

}

cout << " " << tmp <<endl;}
}
I got WA Why?
it works normally...

[Ivchencov]

first line of course is
#include <iostream>

[B.E]

I'm getting a wrong answer.

Code: Select all

//3n+1 problem


#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
 	long i,j;
 	long tmp,current_length,Longest_Length;
 	Longest_Length = 0;
	cin >> i >> j;
 	cout << i << " " << j << " ";
 	if (i > j)
 	{
 	   i ^= j;
 	   j ^=i;
 	   i ^=j;
               }
 	for (;i <= j;i++)
 	{

	 	tmp = i;
	 	current_length = 1;
	 	while (tmp != 1)
	 	{
		 	  if ((tmp & 1)==1)
			   	tmp = 3*tmp + 1;
		   	  else
		   	  	  tmp /= 2;
  		      current_length++;		      
	    }
	    
   		if (Longest_Length < current_length)
   	       Longest_Length = current_length;
	 	
	}
	
	cout << Longest_Length << endl;
    return 0;
}

[shamim]

your are processing a single case, but there will be multiple case in the input file.