100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

What is this ????

Post by 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
New poster
Posts: 1
Joined: Sun Dec 05, 2004 12:57 am
Location: BRASIL (Vit

Please Helpme - Time Limit Exceeded

Post by 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
New poster
Posts: 1
Joined: Wed Dec 08, 2004 8:04 pm

Plz Help me !!!!

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: Plz Help me !!!!

Post by chunyi81 »

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
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
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz »

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

Post by 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
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm

Post by 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
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm

Post by 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
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang »

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);
   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
New poster
Posts: 3
Joined: Sun Jan 02, 2005 3:31 pm

Post by 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
New poster
Posts: 4
Joined: Sat Jan 08, 2005 9:19 pm

100

Post by 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
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

start and end

Post by 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.
Neo

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

Post by enochcheng »

fixed
thx a lot

skw
New poster
Posts: 1
Joined: Sun Jan 23, 2005 2:03 pm

Post by 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
New poster
Posts: 1
Joined: Thu Jan 27, 2005 10:07 pm

Time out on problem 100

Post by 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();}}}

Post Reply

Return to “Volume 1 (100-199)”