## 100 - The 3n + 1 problem

Moderator: Board moderators

Insidetheasylum
New poster
Posts: 2
Joined: Wed Feb 09, 2005 5:24 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:
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!

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

Sorry, I didn't see the sticky. 59446TY
New poster
Posts: 1
Joined: Sat Mar 19, 2005 4:14 am

### The reason 100 doesn't work for most in Java

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

### Problem 100 again...

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

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{
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
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
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
first line of course is
#include <iostream>

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 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;
}``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
your are processing a single case, but there will be multiple case in the input file.