100 - The 3n + 1 problem

[Joseph Kurniawan]

I recently read a post in this volume about this prob. I've checked also the problemstat and to my astonishment this prob can be solved with all the numbers in CPU time ZERO !!!
How did they do that????
Anyone care to share special tricks, hints, or maybe even algo??
Thanx !

[Joseph Kurniawan]

Actually I've posted this in the sticky post, but got no replies. I'm just wondering the way people got AC in such short time. Anyone care to share some special tricks, hints or maybe even algo??
Thanx in advance!!

[Cosmin.ro]

You can use memoization for fast calculating every cycle length for n=1 to 1000000. The number of intervals in wich the result is asked is smaller than 1000, so you can store the intervals and sort their endpoints. In O(n) you can get the maximum value in each interval (xi,xi+1). Now you can get the answer for each query interval in O(n) if you scan the intervals in the sorted order.

[Joseph Kurniawan]

Thnx for the tip !!!!
I'll try that asap!!

[bignad98]

I don't know an elegant way to control a loop based on reaching the end-of-file of the standard input. I think this is the reason I got consistent WA's on problem 100, so I gave up until the same thing comes up on 118.

For 100 i was doing

int firstnum, lastnum;
while( cin>>firstnum>>lastnum)

but the loop never ends until i enter a non-integer value, and i think the judge wants something else. is there any other way besides reading the input stream character by character or line by line and breaking it into tokens?

(i'm a mostly self-taught novice, forgive me)

[bugzpodder]

what you did was fine. if your code ran more than 10 seconds, most likely its either your algorithm is too slow, or that you have an infinite loop somewhere

[Mage]

I don't understand with the cycle_length -> between integer i and j, what is this mean?
Please tell me if anyone know about it. Thanks

[Joseph Kurniawan]

For the num 22, we get the sequence of 16 numbers:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
thus the cycle length for 22 is 16.
So for the prob, you're asked to count the max cycle between the range i to j.

[OmShanti]

I don't know what is wrong:[pascal]program program100;
const
Niesk=0;
var
tab: array[1..1000000] of qword;

i,j,k,h,p: longint;
max,printed: qword;
function oblicz(num: longint): qword;
var
p: qword;
begin
if tab[num]>niesk then
p:=tab[num]
else
if (num mod 2) = 1 then
p:= oblicz(3*num + 1)+1
else
p:= oblicz(num div 2)+1;
{ writeln(num);}
tab[num]:=p;
oblicz:=p;
end;

begin
for i:=1 to 1000000 do
tab:= niesk;
tab[1]:=1;
while not(eof) do
begin
max:=0;
readln(i,j);
p:=0;
if i>j then
begin
h:=i;
i:=j;
j:=h;
p:=1;
end;
for k:=i to j do
begin
{ writeln('****');
writeln('*',k:2,'*');
writeln('****');}
printed:= oblicz(k);
{ writeln(printed);}
if printed>max then
max:=printed;
end;
if p=0 then
writeln(i,' ',j,' ',max)
else
writeln(j,' ',i,' ',max);
end;
end.
[/pascal]

[Ivor]

you must not change the order of the input values...

[OmShanti]

I don't:[pascal]p:=0;
if i>j then
begin
h:=i;
i:=j;
j:=h;
p:=1;
end;
...
if p=0 then
writeln(i,' ',j,' ',max)
else
writeln(j,' ',i,' ',max); {the order was changed earlier}[/pascal]

[Eduard]

please answer to my question if you you solve the problem 100.
Du you solve this program only whith longint?i whant to say that when i give 133381 number to my problem after some time he got a number bigen then maximum longint.Do you solve it using array, to get big numbers?or...
please answer

[Maarten]

I solved the problem using "long long" data type in C++.. not sure if it's really necessary though

[Maarten]

I know nothing about pascal, but i suggest you do the input/output as follows (pseudocode):

Code: Select all

read i, j;
write i, j;
if( i< j ) swap i,j;
compute max
write max

[Maarten]

also, please give your variables english names, it makes your code easier to understand for us...
I think your code doesn't handle correctly the case that your sequence is bigger than 10^6, for example
999999 2999998 1499999 etc.