ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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.