100  The 3n + 1 problem
Moderator: Board moderators

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

 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..
Check out http://www.algorithmist.com !
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
readln(i, j);
write(i, ' ', j, ' ');
if i < j then
writeln(getMaxCL(i, j))
else
writeln(getMaxCL(j, i));
end;
end.
Wrong answer with problem 100
Sorry, I didn't see the sticky.
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 nonworking java submissions.
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 nonworking java submissions.
David

 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
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==x1)
{
counter= counter + cltemp;
break;
}
}
return counter;
}
Problem 100 again...
I submited the following code with Submitomatic 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 ; }
I think tour error is in
you are missing an "<< endl", thus you print two numbers concateneted (that's why it's not P.E.)
Code: Select all
if (i>j) cout << maxOrbit(j,i) ;
Understanding a problem in a natural way will lead to a natural solution
[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{
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.
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.
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...
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...
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;
}