Solution UVA: 701 - The Archeologists’ Dilemma

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss701 - The Archeologists' Dilemma	Accepted	C++11	0.030	0.000	971	3 mins ago

Suggest: (from UVa Problem Solution: 701 - The Archaeologist's Dilemma - 台部落 (twblogs.net))

Let P denotes the prefix, T denotes the # of lost digits. We are searching for N, that the prefix of 2^N is P.

We have an inequlity of

    P*10^T <= 2^N < (P+1)*10^T

thus

    log2(P*10^T) <= log2(2^N) < log2((P+1)*10^T),

which is

    log2(P)+T*log2(10) <= N < log2(P+1)+T*log2(10).

Also, we know that

    P < 10^(T-1),

that is

    T > log10(P)+1.

Then, we can brute force on T and find the minmum N.

#include <bits/stdc++.h>

#define int long long

using namespace std;

int32_t main() {

        ios::sync_with_stdio(0); cin.tie(0);

        int n, p;

        while(cin >> p){

                int T = log10(p) + 2;

               

                for(int t=T; ;t++){

       

                        int l = ceil(log2(p) + t*log2(10));

                        int r = floor(log2(p+1) + t*log2(10));

                        if (l<=r){

                                cout<<l<<"\n";

                                break;

                        }

                }

               

        }

}