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

Insidetheasylum
New poster
Posts: 2
Joined: Wed Feb 09, 2005 5:24 pm

Post by Insidetheasylum » Thu Feb 10, 2005 7:15 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Feb 24, 2005 11:48 pm

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

nicu_ivan
New poster
Posts: 7
Joined: Wed Mar 16, 2005 7:27 pm

Re: If you get WA in problem 100, read me before post!

Post by nicu_ivan » Thu Mar 17, 2005 5:26 pm

This problem is really tuff, even if it is the first one, anyway here is a source code, it got AC.
Source code, got AC wrote: 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
New poster
Posts: 1
Joined: Thu Mar 17, 2005 7:53 pm

Wrong answer with problem 100

Post by _davidf » Thu Mar 17, 2005 7:56 pm

Sorry, I didn't see the sticky.

:oops:

59446TY
New poster
Posts: 1
Joined: Sat Mar 19, 2005 4:14 am

The reason 100 doesn't work for most in Java

Post by 59446TY » Sat Mar 19, 2005 4:23 am

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.
David

wintersoul
New poster
Posts: 1
Joined: Sat Apr 09, 2005 6:59 pm

Post by wintersoul » Sat Apr 09, 2005 7:05 pm

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 :o

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
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

Problem 100 again...

Post by Grazyna » Wed Apr 20, 2005 2:51 pm

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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr » Wed Apr 20, 2005 5:18 pm

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.)
Understanding a problem in a natural way will lead to a natural solution

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

Post by Grazyna » Wed Apr 20, 2005 8:34 pm

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

ppponline
New poster
Posts: 1
Joined: Sun May 08, 2005 12:31 pm

[Java] 100 , Wrong answer?... Who can help me?

Post by ppponline » Sun May 08, 2005 12:35 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun May 08, 2005 4:09 pm

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
New poster
Posts: 3
Joined: Sun Apr 24, 2005 12:21 am

Post by Ivchencov » Fri May 20, 2005 2:07 am

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
New poster
Posts: 3
Joined: Sun Apr 24, 2005 12:21 am

Post by Ivchencov » Fri May 20, 2005 2:09 am

first line of course is
#include <iostream>

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am

Post by B.E » Tue May 24, 2005 5:53 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue May 24, 2005 9:09 am

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

Post Reply

Return to “Volume 1 (100-199)”