## 100 - The 3n + 1 problem

Moderator: Board moderators

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:

### What is this ????

I don't understand, the problem is easy.
the must dificult is when i < j or j > i.
you code is a spaghetti, you need help realy !!!jajajaja

Bayron
New poster
Posts: 1
Joined: Sun Dec 05, 2004 12:57 am
Location: BRASIL (Vit

What is problem?
The Status ever is "Time Limit Exceeded".
Tankyou...

[pascal]
program problema100_volume1;
var
I,J,C,N,CONT,AUX:longint;
begin
while(not eof) do
begin
if (I<1000000) and (I>0) and (J<1000000) and (J>0) then
begin
write(I,' ',J,' ');
if I > J then
begin
AUX:= I;
I:= J;
J:= AUX;
end;
for C:=I to J do
begin
N:=C;
AUX:= 0;
repeat
inc(AUX);
if N=1 then
break
else
if (N mod 2) <> 0 then
N:= (3*N)+1
else
N:=N div 2;
until N <= 0;
if AUX > CONT then
CONT:= AUX;
end;
write(CONT);
end;
end;
end.
[/pascal]

phongtran
New poster
Posts: 1
Joined: Wed Dec 08, 2004 8:04 pm

### Plz Help me !!!!

I still have problem with my code. it got WA. can anybody help me. Thanks you so much !!!
[pascal]
program problem_100 (input,output);
type
arr = array [1..1000000] of longint;
var
a : arr;

function compute(n : longint) : longint;
var count : longint;
begin
count := 1;
repeat
if n = 1 then
begin
compute := count;
exit;
end;
if odd(n) then
n := 3*n + 1
else
n := n div 2;
inc(count);
until false;
end;

function max_in(i,j : longint) : longint;
var max,k : longint;
begin
max := 0;
for k := i to j do
if max < a[k] then
max := a[k];
max_in := max;
end;

procedure solve;
var i,j,k : longint;
begin
fillchar(a,sizeof(a),0);
repeat
for k := i to j do
if a[k] = 0 then
a[k] := compute(k);
k := max_in(i,j);
writeln(i,#32,j,#32,k);
until eof;
end;

begin
solve;
end.
[/pascal]

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### Re: Plz Help me !!!!

phongtran wrote:I still have problem with my code. it got WA. can anybody help me. Thanks you so much !!!
[pascal]
program problem_100 (input,output);
type
arr = array [1..1000000] of longint;
var
a : arr;

function compute(n : longint) : longint;
var count : longint;
begin
count := 1;
repeat
if n = 1 then
begin
compute := count;
exit;
end;
if odd(n) then
n := 3*n + 1
else
n := n div 2;
inc(count);
until false;
end;

function max_in(i,j : longint) : longint;
var max,k : longint;
begin
max := 0;
for k := i to j do
if max < a[k] then
max := a[k];
max_in := max;
end;

procedure solve;
var i,j,k : longint;
begin
fillchar(a,sizeof(a),0);
repeat
for k := i to j do
if a[k] = 0 then
a[k] := compute(k);
k := max_in(i,j);
writeln(i,#32,j,#32,k);
until eof;
end;

begin
solve;
end.
[/pascal]
i can be greater than j, handle that in your code and your code should work fine. Next time check through your code and the forum for threads related for your problem first.

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
Sohel, Congratulations here for your recent result in International and National Programming Contests.
6th in ICPC 2004
3rd in NCPC 2004

Niaz
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

blank3
New poster
Posts: 3
Joined: Mon Dec 13, 2004 12:05 am
Hi ppl!

I cant figure out, what have I done wrong. If I paste the test input:

1 10
100 200
201 210
900 1000

I always have to press <ENTER> to process the last input. Ideas appreciated!

Code: Select all

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

class Main {
void Begin () {
String in;
int p, q, i;
boolean Reversed;

while ((in= ReadLn(20)) != null) {
Reversed= false;

i= in.indexOf(' ');
p= Integer.parseInt(in.substring(0, i));
q= Integer.parseInt(in.substring(++i, in.length()));

if (p > q) {
int tmp= q;
q= p;
p= tmp;
Reversed= true;
}

cycleLength(p, q, Reversed);
}
}

static void cycleLength(int p, int q, boolean Reversed) {
int MaxCycleLength= 0;
int Count, n;

for (int i= p; i<=q;i++) {
Count= 1;
n= i;

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

Count++;
}

if (Count > MaxCycleLength) {
MaxCycleLength= Count;
}
}

if (Reversed == false) {
System.out.println(p+" "+q+" "+MaxCycleLength);
} else {
System.out.println(q+" "+p+" "+MaxCycleLength);
}
}

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

try
{
while (lg < maxLg)
{
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 static void main (String args[])  // entry point from OS
{
Main myWork = new Main();  // create a dinamic instance
myWork.Begin();
}
}
``````

QwertyKzk
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm
T_T
I get WA, shy ((

Code: Select all

``````var N1,N2,solve1:longint;
function Solve(N,k:longint):longint;
var i,j,res:longint;
begin
solve1:=0;
FOR j:=n TO k DO
begin
i:=j;
Res:=0;
while i>1 do
begin
if odd(i) then i:=i*3+1
else I:=I div 2;
Inc(res);
end;
if res>solve1 then solve1:=res
end;
result:=solve1;
end;
begin
while not eof do
begin
Write(N1,' ',N2,' ',Solve(n1,n2)+1);
end;
end.
``````
?????
I can't un derstand why ( ?

QwertyKzk
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm

Code: Select all

``````program problem_100;
var N1,N2,count,solve1:longint;
mass1,mass2,mass3:array[1..100] of longint;
function Solve(N,k:longint):longint;
var i,j,res:longint;
begin
solve1:=0;
FOR j:=n TO k DO
begin
i:=j;
Res:=0;
while i>1 do
begin
if odd(i) then i:=i*3+1
else I:=I div 2;
Inc(res);
end;
if res>solve1 then solve1:=res
end;
result:=solve1;
end;
begin
count:=0;
while not eof do
begin
inc(count);
mass1[count]:=N1;
mass2[count]:=N2;
mass1[count]:=Solve(n1,N2)+1;
end;

for N1:=1 to count do Write(mass1[n1],' ',mass2[n1],' ',mass3[n1]);
Writeln;
end.
``````
((((( Who can say, why WA?

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am
QwertyKzk wrote:

Code: Select all

``````program problem_100;
var N1,N2,count,solve1:longint;
mass1,mass2,mass3:array[1..100] of longint;
function Solve(N,k:longint):longint;
var i,j,res:longint;
begin
solve1:=0;
FOR j:=n TO k DO
begin
i:=j;
Res:=0;
while i>1 do
begin
if odd(i) then i:=i*3+1
else I:=I div 2;
Inc(res);
end;
if res>solve1 then solve1:=res
end;
result:=solve1;
end;
begin
count:=0;
while not eof do
begin
inc(count);
mass1[count]:=N1;
mass2[count]:=N2;
mass1[count]:=Solve(n1,N2)+1;
end;

for N1:=1 to count do Write(mass1[n1],' ',mass2[n1],' ',mass3[n1]);
Writeln;
end.
``````
((((( Who can say, why WA?
Base on reading your code, I see 4 problems. I have not program in PASCAL for more than a decade though.

1. You never assign to mass3
2. You can only handle 100 cases
3. Don't memorize all the answer and print them out at the end
4. n1 > n2 is not handle

QwertyKzk
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm

Code: Select all

``````program p100;
var N1,N2,count,solve1:longint;
mass1,mass2,mass3:array[1..1000000] of longint;
function Solve(N,k:longint):longint;
var i,j,res:longint;
begin
solve1:=0;
if N<K then
Begin
FOR j:=n TO k DO
begin
i:=j;
Res:=0;
while i>1 do
begin
if odd(i) then i:=i*3+1
else I:=I div 2;
Inc(res);
end;
if res>solve1 then solve1:=res
end;
End
else
Begin
FOR j:=k TO n DO
begin
i:=j;
Res:=0;
while i>1 do
begin
if odd(i) then i:=i*3+1
else I:=I div 2;
Inc(res);
end;
if res>solve1 then solve1:=res
end;

End;
result:=solve1;
end;
begin
count:=0;
while not eof do
begin
inc(count);
mass1[count]:=N1;
mass2[count]:=N2;
mass3[count]:=Solve(n1,N2)+1;
end;

for N1:=1 to count do
begin
Write(mass1[n1],' ',mass2[n1],' ',mass3[n1]);
Writeln;
end;
end.``````
I have corrected some mistakes, but all equal does not work. In what there can be a problem? For earlier many thanks!

enochcheng
New poster
Posts: 4
Joined: Sat Jan 08, 2005 9:19 pm

### 100

What's wrong with it?
thx

#include "stdio.h"
main()
{
int i,n,start,end,c,max;
while(scanf("%d%d",&start,&end)==2)
{
max=0;
for(i=start;i<=end;i++)
{
n=i;
c=0;
while(1)
{
c++;
if(n==1)
break;
if(n%2==1)
n=3*n+1;
else
n/=2;
}
if(c>max)
max=c;
}
printf("%d %d %d\n",start,end,max);
}
}

neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

### start and end

I think your only problem is to assume that start<end ..

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j.

Neo

enochcheng
New poster
Posts: 4
Joined: Sat Jan 08, 2005 9:19 pm
fixed
thx a lot

skw
New poster
Posts: 1
Joined: Sun Jan 23, 2005 2:03 pm
could anyone find the mistakes in my code please? I ran it through and it seems to work just fine, but keep getting WA. Thank you!

Code: Select all

``````import java.io.FileInputStream;
import java.io.InputStream;
import java.io.IOException;

import java.util.StringTokenizer;

private InputStream in;

this.in = in;}

public String readLine () throws IOException {
final StringBuffer s = new StringBuffer(255);
int i = 0;
while (((i = in.read()) != '\n') && (i != -1))
if (i != '\r')
s.append((char) i);
if (i == -1)
return null;
return s.toString();}}

final class Main {
static int eval (int i, int j) {
int max = 0, temp = 0;
if(j<i)
{
temp = i;
i = j;
j = temp;
temp = 0;
}
for(int x = i - 1; x <= j; x++)
{
temp = cyclelength(x);
if (max < temp)
max = temp;
}
return max;}
static int cyclelength(int i)
{
int cycle = 1;
while(i != 1)
{
if(i%2 == 1)
{
i=3*i+1;
cycle++;
}
if(i%2 == 0)
{
i = i/2;
cycle++;
}
}
return cycle;
}
static void main (String[] args) {
try {
String   s;
while ((s = in.readLine()) != null) {
StringTokenizer st = new StringTokenizer(s);
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
System.out.println(i + " " + j + " " + eval(i, j));}}
catch (IOException e) {
e.printStackTrace();}}}``````

jared_grau
New poster
Posts: 1
Joined: Thu Jan 27, 2005 10:07 pm

### Time out on problem 100

I cannot for the life of me figure out how i am getting a time out
I have tried long and ints and done this recursively and iteratively
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.IOException;

import java.util.StringTokenizer;

private InputStream in;

this.in = in;}

public String readLine () throws IOException {
final StringBuffer s = new StringBuffer(255);
int i = 0;
while (((i = in.read()) != '\n') && (i != -1))
if (i != '\r')
s.append((char) i);
if (i == -1)
return null;
return s.toString();}}

final class Main {
public static long eval(long m, long n)
{
long big=0;
if(m<=n)
{
for(long t=m;t<=n;t++)
{
long todo=help(t);
if(todo>big)
big=todo;
}
}
else
{
for(long t=n;t<=m;t++)
{
long todo=help(t);
if(todo>big)
big=todo;
}
}
return big;
}
public static long help (long i) {
int cycle=1;
while(i!=1)
{
if(i%2==1)
{
i=3*i+1;
cycle++;}
else
{
i=i/2;
cycle++;
}
}
return cycle;
}

public static void main (String[] args) {
try {