100 - The 3n + 1 problem
Moderator: Board moderators
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
the must dificult is when i < j or j > i.
you code is a spaghetti, you need help realy !!!jajajaja
Please Helpme - Time Limit Exceeded
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]
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]
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
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]
[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]
Re: Plz Help me !!!!
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.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]
-
- 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
6th in ICPC 2004
3rd in NCPC 2004
Niaz
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/
http://groups.yahoo.com/group/acm_solver/
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!
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();
}
}
T_T
I get WA, shy ((
?????
I can't un derstand why ( ?
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 ( ?
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.
-
- New poster
- Posts: 11
- Joined: Sun Jan 02, 2005 9:14 am
Base on reading your code, I see 4 problems. I have not program in PASCAL for more than a decade though.QwertyKzk wrote:((((( Who can say, why WA?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.
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
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.
I have corrected some mistakes, but all equal does not work. In what there can be a problem? For earlier many thanks!
-
- 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);
}
}
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);
}
}
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.
I hope this help you.
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
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();}}}
-
- 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;
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();}}}
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();}}}