100 - The 3n + 1 problem

[23756AW]

Brute force won't work on this. You need to employ some dynamic programming to solve this efficiently. That means you should create an array and store some already solved results. Then when update the ackerman function to do the ackfunct and then check the result to see if it is in the array. If it is then you can simply add the saved result to the current length.

[Adrian Kuegel]

Your problem is here:
while(scanf("%d %d",&n1,&n2))

read man pages for scanf(), you will notice that it returns -1 if it reaches EOF. The proper using of scanf in this case is:
while(scanf("%d %d",&n1,&n2)==2)

[epsilon0]

solved in 3.111 seconds with brute force. is there another way?

btw EOF is -1 on most systems (i think). just use EOF to be sure.

[c]#include <stdio.h>

...

while (scanf("%d %d) != EOF) { ... }[/c]

[epsilon0]

yes you are perfectly right, the judge accepted my program although it did not take care of overflows. perhaps the test input used by the judge doesn't have values that cause an overflow.

the value 159487 is the first one that causes an overflow.
after 59 cycles, we have the number:
1,699,000,271
which clearly causes a problem if you multiply it by 3 on a 32 bit system.

so my program, and the program of your collegue, both output a result that is most likely wrong.

a workaround is as follow:

precompute on your home computer all the values that cause an overflow, and the correct answer for them. then your program check wether there are such values between i and j, and looks up the answers in a table if needed.

it would be too slow to manage large integers in this program.

it's a pity that the test input of the judge doesn't have this special case.

[wrygiel]

yes you are perfectly right
(...)
precompute on your home computer all the values that cause an overflow, and the correct answer for them. then your program check wether there are such values between i and j, and looks up the answers in a table if needed.

it would be too slow to manage large integers in this program.

it's a pity that the test input of the judge doesn't have this special case.

I've send the program with large integers (quadword) and it took about 1.5 seconds to complete the tests. (It was made of 2 longwords). The times (10 seconds!) also are much too large - IMO it should be about 1 second or something like that but not 10!

Maybe it is possible to submit one another test? I mean - just write an email telling them to add that single line to the end of their tests.

[hesper]

Yes, at the very beginning, I assume that it can't overflow

[Miguel Correia Ricardo]

Hi, what's wrong with my code, it gives WRONG ANSWER...

#include <iostream>
#include <algorithm>
using namespace std;

int cycle_length (unsigned int i)
{
unsigned int max=1;

while (i > 1)
{
if (i % 2)
i = 3*i + 1;
else
i /= 2;

max++;
}
return max;
}

int main()
{
unsigned int i,j;
int temp=0;

while (cin >> i >> j){
cout << i << " " << j << " ";
if (i > j) {
temp = i;
i = j;
j = temp;
temp = 0;
}

while (i <= j)
temp = max(temp, cycle_length(i++));
cout << temp << endl;
}
}

[Miguel Correia Ricardo]

I forgot to do temp = 0, outside the if scope...but it still gives wrong answer....

[toks725]

Please check my code:

// @JUDGE_ID: 26390KA 100 Java "The 3n + 1 problem"

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

public class Problem1
{

public int max, counter, aCounter;
public String input, tempA[];
public Vector vector;

public Problem1()
{
vector = new Vector();
tempA = new String[100];
aCounter = 0;
while((input = readLine (255)) != null)
{
if(input.length()>1)
{
StringTokenizer token = new StringTokenizer(input);
int input1 = Integer.parseInt(token.nextToken());
int input2 = Integer.parseInt(token.nextToken());
if(input1>0 && input2>0 && input1<1000000 && input2<1000000)
{
max = 0;
for(int j=input1; j<input2; j++)
{
compute(j);
max = Math.max(max, counter);
}
tempA[aCounter] = (input1 + " " + input2 + " " + max);
aCounter++;
}
else
{
break;
}
}
else break;
}
for(int i=0; i<aCounter; i++)
System.out.println(tempA);
}

public static void main(String args[])
{
Problem1 app = new Problem1();
}

public String readLine(int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public void compute(int i)
{
counter = 1;

while(i!=1)
{
if(i%2==0)
i = i/2;
else i = (3*i)+1;
counter++;
}
}
}

This program was work perfoectly in my computer, but when i submitted throught online system, it returns wrong answer. I don't know why. Please help...

[yiuyuho]

First, your program is way too long for p100, even it is written in java, second I think the judge require the class name to be named "Main" not "Problem 1" you can check the judges re4quirement on java submission to make sure the format is correct. Third, I think all "System" calls are prohibited functions. Forth, you need to check that
input1 < input 2, so you compute all integers "between" them rather than from input1 to input 2, you can simply swap them.

But read the specification to ensure you meet the output requirement.

Finally, you can use StreamTokenizer to get input from problems of this type, it will be much esaier.

[Hovo]

[cpp]

Code: Select all

hhhhhhhhhhhhhhhhhhhhhhheeeeeeeeeeeeeellllllllllllllllllllllllpppppppppppp

[/cpp]

[rjhadley]

It's been a while since I done this problem, but it looks like you'll handle the input 1 1 wrong. The output should be 1 1 1, not 1 1 4. It is your goto statements which are the source of the error - you are checking if j == 1 after you've already done an iteration. goto's are generally frowned upon because they make the flow of the program difficult to follow and are error prone.

You're cin code will work fine, but my personal preference is:
[cpp]
while( true ) {
cin >> a >> b;
if( cin.eof() || cin.fail() ) {
break;
}
[/cpp]
Also, endl is ususally used with cout instead of "\n", but again this is a very minor point. (The endl operator flushes the output buffer as well as printing a newline).

The input values are also always greater than 0 (but if they weren't you should use continue instead of goto).

After these changes you're source code becomes:
[cpp]
#include <iostream>
#include <cstdio>

using namespace std;

void
main()
{
long int a, b, i, j, x, a1, temp;

while( cin>> a >> b ) {
if( a > b ) {
a1 = a;
a = b;
b = a1;
} // if

temp = 0;

for( i = a; i <= b; i++ ) {
j = i;
x = 1;

while( j > 1 ) {
if( j % 2 > 0 ) {
j= ( 3 * j ) + 1;
x++;
} else {
j = j / 2;
x++;
} // if
} // while

if( x > temp ) {
temp = x;
} // if
} // for

if( a1 == b ) {
cout << b << " " << a << " " << temp << endl;
} else {
cout << a << " " << b << " " << temp << endl;
} // if
} // for
} // main()
[/cpp]

I think this will work.

[hsuyt831]

How can I modify my source code??
can someone please help me???
here is my souce code

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

int main()
{
int m,n,i,x=0,a,c,d;

while(scanf("%d%d",&m,&n)==2){
if(m<n){
c=m;
d=n;
}
else{
c=n;
d=m;
}

for(i=c;i<=d;i++){
a=1;
while(i!=1){
if(i%2==1)
i=3*i+1;
else
i=i/2;
a++;
}

if(a>x)
x=a;
}
printf("%d,%d,%d\n",m,n,x);

}
return 0;
}

[Larry]

Try some caching.. =)

Also, I don't see where you reset the value of x, so this may yield a WA anyhow..

[epsilon0]

Larry is right about x.

And also, don't modify i inside the for loop! fool! here i modified your program, it looks like it works now. did you not test it before you sent it to the judge?

[c]#include <stdlib.h>
#include <stdio.h>

int main()
{
int m,n,i,x=0,a,c,d;
int better_this_way;
while(scanf("%d%d",&m,&n)==2){
if(m<n){
c=m;
d=n;
}
else{
c=n;
d=m;
}
x=0;
for(i=c;i<=d;i++){
better_this_way = i;
a=1;
while(better_this_way!=1){
if(better_this_way%2==1)
better_this_way=3*better_this_way+1;
else
better_this_way=better_this_way/2;
a++;
}

if(a>x)
x=a;
}
printf("%d,%d,%d\n",m,n,x);

}
return 0;
}[/c]