100  The 3n + 1 problem
Moderator: Board moderators

 New poster
 Posts: 2
 Joined: Thu Jun 19, 2003 9:28 am
Problem 100: Wrong answer accepted?
I think that the online judge accepted one of my wrong answers.
The data which led me to this belief is this:
500000 500000
1000000 1000000
By right, 1000000 should involved just one more step to generate the answer from 500000, which I think is 152+1=153.
However the judge accepted my program which gave the result as 4199612.
I also noted that the new limit for i and j is now 1 million.
Am I right to say the OJ accepted the wrong answer?
The data which led me to this belief is this:
500000 500000
1000000 1000000
By right, 1000000 should involved just one more step to generate the answer from 500000, which I think is 152+1=153.
However the judge accepted my program which gave the result as 4199612.
I also noted that the new limit for i and j is now 1 million.
Am I right to say the OJ accepted the wrong answer?
mem usage
Odd. I've submitted code for problem 100 with an int array size of 64000 and the mem usage is 600k+. I upped the array size to 100000 to see if the program would run faster and it did, but the mem usage was down to 64k. Does it not work properly? Or am I missing something?
You are not the first one to wonder... and not the last one. Memory usage "depends" on the running time. If your program is fast enough (time less than 0.110/0.100) it might (not necessarily, but usually) have a memory use of 64k even though you had used aboug 5Mb. Above some critical time the judge will show more or less correct estimate. And it aquires about 368400kb for IOroutines. Thus you get 400+64000*4 =~ 600kb.
Ivor
P.S. Search the board  there are many answers to many questions.
Ivor
P.S. Search the board  there are many answers to many questions.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

 New poster
 Posts: 4
 Joined: Tue Jul 29, 2003 10:56 am
problem solving
i have 2 problem's
Problem 100 ( Time limit exceed)

(* @JUDGE_ID: 26310AM 100 Pascal *)
(* @begin_of_source_code *)
program p100(input,output);
var i, j, k, total, max : integer;
procedure detect(number : longint;var total : integer);
begin
inc(total);
if (number <> 1) then
begin
if ((number mod 2) = 1) then number := number*3+1
else number := number div 2;
detect(number,total);
end;
end;
begin
while not eof(input) do
begin
read(input,i); readln(input,j);
if j < i then
begin
k := i; i := j; j := k;
end;
if i < 0 then halt;
if 1000000 < j then halt;
max := 0;
for k := i to j do
begin
total := 0;
detect(k,total);
if (max < total) then max := total;
end;
writeln(output,i:1,' ',j:1,' ',max:1);
end;
end.
(* @end_of_source_code *)

Problem 101 (WA)

(* @JUDGE_ID: 26310AM 101 Pascal *)
(* @begin_of_source_code *)
program p101(input,output);
var b1,b2,command:string;
totpile,bb1,bb2,code,c1,c2,i,j,k,l,m,n,total:integer;
block:array[0..24,0..24] of integer;
success:boolean;
procedure detect;
begin
for i := 0 to total do
for j := 0 to total do
if block[j] = bb1 then
begin
k := i;
l := j;
end;
end;
procedure detect2;
begin
for i := 0 to total do
for j := 0 to total do
if block[j] = bb2 then
begin
m := i;
n := j;
end;
end;
procedure count;
begin
totpile := 0;
for i := l to total do
if block[k] <> 1 then inc(totpile);
end;
begin
readln(input,total);
if 25 < total then halt
else if total < 0 then halt;
for i := 0 to 24 do for j := 0 to 24 do block[j] := 1;
for i := 1 to total do block[i1][0] := i1;
command := '';
while not (command = 'quit') do
begin
readln(input,command);
c1:=0;c2:=0;b1:='';b2:='';
if(copy(command,1,4)='move') then c1 := 1
else if(copy(command,1,4)='pile') then c1 := 2;
b1 := copy(command,6,1);
if(copy(command,8,4)='onto') then c2 := 1
else if(copy(command,8,4)='over') then c2 := 2;
b2 := copy(command,13,1);
val(b1,bb1,code);
val(b2,bb2,code);
case c1 of
1:case c2 of
1:
begin
detect;
detect2;
if block[m][n+1] = 1 then block[m][n+1] := block[k][l]
else
begin
for i := total downto n+2 do block[m] := block[m][i1];
block[m][n+1] := block[k][l];
end;
if block[k][l+1] = 1 then block[k][l] := 1
else
for j := l to total1 do
block[k][j] := block[k][j+1];
end;
2:
begin
detect;
detect2;
for i := 0 to total do
if block[m] = 1 then
begin
block[m] := block[k][l];
if block[k][l+1] = 1 then block[k][l] := 1
else
for j := l to total1 do
block[k][j] := block[k][j+1];
end;
end;
end;
2:case c2 of
1:
begin
detect;
detect2;
count;
if block[m][n+1] = 1 then
for i := l to l+totpile1 do
begin
success := false;
for j := n+1 to total do
if (not success) and (block[m][j] = 1) then
begin
block[m][j] := block[k];
block[k] := 1;
success := true;
end;
end
else
begin
for i := total downto n+totpile+1 do block[m] := block[m][itotpile];
for i := 1 to totpile do
begin
block[m][n+i] := block[k][l+i1];
block[k][l+i1] := 1;
end;
end;
end;
2:
begin
detect;
detect2;
count;
for i := l to l+totpile1 do
begin
success := false;
for j := n+1 to total do
if (not success) and (block[m][j] = 1) then
begin
block[m][j] := block[k][i];
block[k][i] := 1;
success := true;
end;
end;
end;
end;
end;
end;
for i := 0 to total1 do
begin
write(i:1,': ');
for j := 0 to total1 do
begin
if (block[i][j] <> 1) then
begin
if j = 0 then write(block[i][j])
else write(' ',block[i][j]);
end;
end;
writeln;
end;
end.
(* @end_of_source_code *)

Why? Please tell me how to solve it.
I think all of them are allright.
ASAP. Thanks.
Problem 100 ( Time limit exceed)

(* @JUDGE_ID: 26310AM 100 Pascal *)
(* @begin_of_source_code *)
program p100(input,output);
var i, j, k, total, max : integer;
procedure detect(number : longint;var total : integer);
begin
inc(total);
if (number <> 1) then
begin
if ((number mod 2) = 1) then number := number*3+1
else number := number div 2;
detect(number,total);
end;
end;
begin
while not eof(input) do
begin
read(input,i); readln(input,j);
if j < i then
begin
k := i; i := j; j := k;
end;
if i < 0 then halt;
if 1000000 < j then halt;
max := 0;
for k := i to j do
begin
total := 0;
detect(k,total);
if (max < total) then max := total;
end;
writeln(output,i:1,' ',j:1,' ',max:1);
end;
end.
(* @end_of_source_code *)

Problem 101 (WA)

(* @JUDGE_ID: 26310AM 101 Pascal *)
(* @begin_of_source_code *)
program p101(input,output);
var b1,b2,command:string;
totpile,bb1,bb2,code,c1,c2,i,j,k,l,m,n,total:integer;
block:array[0..24,0..24] of integer;
success:boolean;
procedure detect;
begin
for i := 0 to total do
for j := 0 to total do
if block[j] = bb1 then
begin
k := i;
l := j;
end;
end;
procedure detect2;
begin
for i := 0 to total do
for j := 0 to total do
if block[j] = bb2 then
begin
m := i;
n := j;
end;
end;
procedure count;
begin
totpile := 0;
for i := l to total do
if block[k] <> 1 then inc(totpile);
end;
begin
readln(input,total);
if 25 < total then halt
else if total < 0 then halt;
for i := 0 to 24 do for j := 0 to 24 do block[j] := 1;
for i := 1 to total do block[i1][0] := i1;
command := '';
while not (command = 'quit') do
begin
readln(input,command);
c1:=0;c2:=0;b1:='';b2:='';
if(copy(command,1,4)='move') then c1 := 1
else if(copy(command,1,4)='pile') then c1 := 2;
b1 := copy(command,6,1);
if(copy(command,8,4)='onto') then c2 := 1
else if(copy(command,8,4)='over') then c2 := 2;
b2 := copy(command,13,1);
val(b1,bb1,code);
val(b2,bb2,code);
case c1 of
1:case c2 of
1:
begin
detect;
detect2;
if block[m][n+1] = 1 then block[m][n+1] := block[k][l]
else
begin
for i := total downto n+2 do block[m] := block[m][i1];
block[m][n+1] := block[k][l];
end;
if block[k][l+1] = 1 then block[k][l] := 1
else
for j := l to total1 do
block[k][j] := block[k][j+1];
end;
2:
begin
detect;
detect2;
for i := 0 to total do
if block[m] = 1 then
begin
block[m] := block[k][l];
if block[k][l+1] = 1 then block[k][l] := 1
else
for j := l to total1 do
block[k][j] := block[k][j+1];
end;
end;
end;
2:case c2 of
1:
begin
detect;
detect2;
count;
if block[m][n+1] = 1 then
for i := l to l+totpile1 do
begin
success := false;
for j := n+1 to total do
if (not success) and (block[m][j] = 1) then
begin
block[m][j] := block[k];
block[k] := 1;
success := true;
end;
end
else
begin
for i := total downto n+totpile+1 do block[m] := block[m][itotpile];
for i := 1 to totpile do
begin
block[m][n+i] := block[k][l+i1];
block[k][l+i1] := 1;
end;
end;
end;
2:
begin
detect;
detect2;
count;
for i := l to l+totpile1 do
begin
success := false;
for j := n+1 to total do
if (not success) and (block[m][j] = 1) then
begin
block[m][j] := block[k][i];
block[k][i] := 1;
success := true;
end;
end;
end;
end;
end;
end;
for i := 0 to total1 do
begin
write(i:1,': ');
for j := 0 to total1 do
begin
if (block[i][j] <> 1) then
begin
if j = 0 then write(block[i][j])
else write(' ',block[i][j]);
end;
end;
writeln;
end;
end.
(* @end_of_source_code *)

Why? Please tell me how to solve it.
I think all of them are allright.
ASAP. Thanks.

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
Two equal programs. One AC other WA ??
Here are two programs that do exactly the same thing.
This one is accepted...
[java]
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
String in;
while((in = readLine(512)) != null) {
StringTokenizer st = new StringTokenizer(in);
int low = Integer.parseInt(st.nextToken());
int high = Integer.parseInt(st.nextToken());
solve(low, high);
}
}
static void solve(int l, int h) {
int low = Math.min(l, h);
int high = Math.max(l, h);
int solution = 0;
int count;
for(int i = low; i <=high; i++) {
int n = i;
count = 1;
while(n != 1) {
if(n%2 != 0) n = 3*n + 1;
else n = n/2;
count++;
}
if(count > solution) solution = count;
}
System.out.println(l + " " + h + " " + solution);
}
static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = 1;
while(lg < maxLg) {
car = System.in.read();
if(car<0  car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg);
}
}
[/java]
This one is not... (???????????)
[java]
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
String in;
while((in = readLine(512)) != null) {
StringTokenizer st = new StringTokenizer(in);
solve(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
);
}
}
static void solve(int l, int h) {
int count, solution = 0;
for(int i = Math.min(l,h); i <= Math.max(l,h); i++) {
int n = i;
count = 1;
while(n != 1) {
if(n%2 != 0) n = 3*n + 1;
else n /= 2;
count++;
}
if(count > solution) solution = count;
}
System.out.println(l + " " + h + " " + solution);
}
static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = 1;
while(lg < maxLg) {
car = System.in.read();
if(car<0  car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg);
}
}
[/java]
Anyone know why these two programs, which are practically identical, give different results? (Actually, for a large data set, my programs output two EXACTLY ALIKE outputs. So I don't know what's going on.)
This one is accepted...
[java]
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
String in;
while((in = readLine(512)) != null) {
StringTokenizer st = new StringTokenizer(in);
int low = Integer.parseInt(st.nextToken());
int high = Integer.parseInt(st.nextToken());
solve(low, high);
}
}
static void solve(int l, int h) {
int low = Math.min(l, h);
int high = Math.max(l, h);
int solution = 0;
int count;
for(int i = low; i <=high; i++) {
int n = i;
count = 1;
while(n != 1) {
if(n%2 != 0) n = 3*n + 1;
else n = n/2;
count++;
}
if(count > solution) solution = count;
}
System.out.println(l + " " + h + " " + solution);
}
static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = 1;
while(lg < maxLg) {
car = System.in.read();
if(car<0  car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg);
}
}
[/java]
This one is not... (???????????)
[java]
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
String in;
while((in = readLine(512)) != null) {
StringTokenizer st = new StringTokenizer(in);
solve(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
);
}
}
static void solve(int l, int h) {
int count, solution = 0;
for(int i = Math.min(l,h); i <= Math.max(l,h); i++) {
int n = i;
count = 1;
while(n != 1) {
if(n%2 != 0) n = 3*n + 1;
else n /= 2;
count++;
}
if(count > solution) solution = count;
}
System.out.println(l + " " + h + " " + solution);
}
static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = 1;
while(lg < maxLg) {
car = System.in.read();
if(car<0  car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg);
}
}
[/java]
Anyone know why these two programs, which are practically identical, give different results? (Actually, for a large data set, my programs output two EXACTLY ALIKE outputs. So I don't know what's going on.)
Time limit exceeded in problem 100
hi,
would anybody please tell me why do I get Time limit exceeded for the 3n+1 problem. here is my code:
[cpp]#include <iostream.h>
#include <fstream.h>
ifstream in;
void main(){
in.open("in.txt");
int i,j;
long max;
long x,y;
while(!in.eof())
{
in>>x>>y;
cout<<x<<' '<<y<<' ';
if (x>y)
{
long t=x;
x=y;
y=t;
}
max=0;
for(j=x; j<=y; j++)
{
long c=1;
i=j;
while (i!=1)
{
c++;
i=(i%2==1)? 3*i+1 : i/2;
}
if (max<c) max=c;
}
cout<<max<<endl;
}
in.close();
}[/cpp]
thnx
would anybody please tell me why do I get Time limit exceeded for the 3n+1 problem. here is my code:
[cpp]#include <iostream.h>
#include <fstream.h>
ifstream in;
void main(){
in.open("in.txt");
int i,j;
long max;
long x,y;
while(!in.eof())
{
in>>x>>y;
cout<<x<<' '<<y<<' ';
if (x>y)
{
long t=x;
x=y;
y=t;
}
max=0;
for(j=x; j<=y; j++)
{
long c=1;
i=j;
while (i!=1)
{
c++;
i=(i%2==1)? 3*i+1 : i/2;
}
if (max<c) max=c;
}
cout<<max<<endl;
}
in.close();
}[/cpp]
thnx