ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1318. Logarithm

Very interesting problem (+)
Posted by Dmitry 'Diman_YES' Kovalioff 14 Sep 2004 15:30
...And not as difficult as it seems to be. My program on Pascal gets AC within 0.796 sec without complicated optimizations and even without sorting, grouping, ets. Just some good precalc ideas realized properly :)
Re: Very interesting problem (+)
Posted by Tolstobrov_Anatoliy[Ivanovo SPU] 21 Aug 2005 21:56

Dima, I better
901327    21:51:38
21 авг 2005    Anatoliy 'Tolyan_NO' Tolstobroff    1318    Pascal    Accepted
0.687    281 КБ

Not use binaru searching use O(39), but cleaver.
Re: Very interesting problem (+)
Posted by GaLL 31 Aug 2005 22:50
My solution uses additional array [65536] that helps to calculate int(log2()) of 16-bit numbers faster.
GaLL 1318 C++ Accepted 0.406 314 КБ
Re: Very interesting problem (+)
Posted by Sergey M. Masloboev 14 Sep 2006 14:02
Optimized binary searching:
no extras comparisons, no cycles
6 comparisons only !!!

int Find( Tm_LargeNumber<> &n )
{
if (n < Pow[16])
if (n < Pow[8])
if (n < Pow[4])
if (n < Pow[2])
if (n < Pow[1])
return 0;
else
return 1;
else
if (n < Pow[3])
return 2;
else
return 3;
else
if (n < Pow[6])
if (n < Pow[5])
return 4;
else
return 5;
else
if (n < Pow[7])
return 6;
else
return 7;
else
if (n < Pow[12])
if (n < Pow[10])
if (n < Pow[9])
return 8;
else
return 9;
else
if (n < Pow[11])
return 10;
else
return 11;
else
if (n < Pow[14])
if (n < Pow[13])
return 12;
else
return 13;
else
if (n < Pow[15])
return 14;
else
return 15;
else
if (n < Pow[32])
if (n < Pow[24])
if (n < Pow[20])
if (n < Pow[18])
if (n < Pow[17])
return 16;
else
return 17;
else
if (n < Pow[19])
return 18;
else
return 19;
else
if (n < Pow[22])
if (n < Pow[21])
return 20;
else
return 21;
else
if (n < Pow[23])
return 22;
else
return 23;
else
if (n < Pow[28])
if (n < Pow[26])
if (n < Pow[25])
return 24;
else
return 25;
else
if (n < Pow[27])
return 26;
else
return 27;
else
if (n < Pow[30])
if (n < Pow[29])
return 28;
else
return 29;
else
if (n < Pow[31])
return 30;
else
return 31;
else
if (n < Pow[36])
if (n < Pow[34])
if (n < Pow[33])
return 32;
else
return 33;
else
if (n < Pow[35])
return 34;
else
return 35;
else
if (n < Pow[37])
return 36;
else
if (n < Pow[38])
return 37;
else
return 38;
}
Re: Very interesting problem (+)
Posted by Al.Cash 8 Jun 2009 16:18
I think it's much more interesting to find O(n) solution.
It is really beautiful.