100 - The 3n + 1 problem

[Boss]

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]

Please Help me.
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
read(I,J);
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]

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
readln(i,j);
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]

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
readln(i,j);
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]

Sohel, Congratulations here for your recent result in International and National Programming Contests.
6th in ICPC 2004
3rd in NCPC 2004

Niaz

[blank3]

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

[QwertyKzk]

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
   read(N1);
   Read(n2);
   Write(N1,' ',N2,' ',Solve(n1,n2)+1);
 end;
end.

?????
I can't un derstand why ( ?

[QwertyKzk]

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);
   read(N1);
   Read(n2);
   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]

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);
   read(N1);
   Read(n2);
   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]

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); 
   read(N1); 
   Read(n2); 
   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.

Thanks for the previous answer.
I have corrected some mistakes, but all equal does not work. In what there can be a problem? For earlier many thanks!

[enochcheng]

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]

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.

I hope this help you.

[enochcheng]

fixed
thx a lot

[skw]

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;

interface MyReader {
    String readLine () throws IOException;}

final class MyBufferedReader implements MyReader {
    private InputStream in;

    public MyBufferedReader (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 {
            MyReader in = new MyBufferedReader(System.in);
            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]

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;

interface MyReader {
String readLine () throws IOException;}

final class MyBufferedReader implements MyReader {
private InputStream in;

public MyBufferedReader (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 {
MyReader in = new MyBufferedReader(System.in);
/*
MyReader in = new MyBufferedReader(new FileInputStream("main.in"));
*/
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();}}}