100 - The 3n + 1 problem

[project_00]

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]

Am I right to say the OJ accepted the wrong answer?

You may want to post your source code here.

[paulhryu]

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]

Try to indent the code, it certainly will help to understand the code more easily...

Nuno Pereira

[shamim]

I identified one problem.

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

[awik_10]

thank you anyway , i've got accepted because of all your suggestion.
best regards,
awik

[kimpton]

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]

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.

[secret-mission]

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[i-1][0] := i-1;
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][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]

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

[xbeanx]

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]

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]

You have to read from stdin, not "input.txt".

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

[Joe]

I got correct answer, thank you xbeanx

[El-idioto]

Hi Secret-Mission,

Please use the [cpp] syntax highlighting.
Your code is positively unreadable like this.

Sander