## 100 - The 3n + 1 problem

Moderator: Board moderators

project_00
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?

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
Am I right to say the OJ accepted the wrong answer?
You may want to post your source code here.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Accepted doesn't mean your program's right. It just means your program got every test case correctly that the judge decided to throw at it.

Don't confuse the two: accepted does not mean right.

And I wonder, sometimes right does not mean accepted either... Some of these judgings are highly doubtful.

bigs
New poster
Posts: 1
Joined: Mon Jun 23, 2003 3:25 am
Location: Portugal
Contact:
Try to indent the code, it certainly will help to understand the code more easily...

Nuno Pereira

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I identified one problem.

all of your output comes on a single line.
Each output should be on a separate line.

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am
thank you anyway , i've got accepted because of all your suggestion.
best regards,
awik

kimpton
New poster
Posts: 1
Joined: Sat Jul 26, 2003 6:18 pm

### 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?

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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 368-400kb for IO-routines. Thus you get 400+64000*4 =~ 600kb.

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.

secret-mission
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
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
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[i-1] := i-1;
command := '';
while not (command = 'quit') do
begin
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][i-1];
block[m][n+1] := block[k][l];
end;
if block[k][l+1] = -1 then block[k][l] := -1
else
for j := l to total-1 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 total-1 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+totpile-1 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][i-totpile];
for i := 1 to totpile do
begin
block[m][n+i] := block[k][l+i-1];
block[k][l+i-1] := -1;
end;
end;
end;
2:
begin
detect;
detect2;
count;
for i := l to l+totpile-1 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 total-1 do
begin
write(i:1,': ');
for j := 0 to total-1 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.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm

### 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) {
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) {
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.)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
I found out why one is WA... GCJ does its embedded functions backwards. The Java SDK, when encountering f(g(), h()) evals g then h then f. GCJ evals it h, then g, then f.

That's why my 2 codes, which have identical logic, gave different answers.

Joe
New poster
Posts: 6
Joined: Fri Aug 08, 2003 2:06 pm
Location: Egypt

### 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 xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
You have to read from stdin, not "input.txt".

Change that "in>>x" to "cin>>x" and I bet it'll be okay.

Joe
New poster
Posts: 6
Joined: Fri Aug 08, 2003 2:06 pm
Location: Egypt

### thnx

I got correct answer, thank you xbeanx El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Hi Secret-Mission,

Please use the [cpp] syntax highlighting.