701 - The Archeologists' Dilemma

[brunokbcao]

Thanks... I was using strings

[atif_ilm]

I don't remember exactly but main idea is to use logs. We're searching x, and there must be

N*10^k <= 2^x and 2^x < (N+1)*10^k, k -- number of missed digits, so
log2(N*10^k) <= log2(2^x) and log2(2^x) < log2((N+1)*10^k)
log2(N) + k*log2(10) <= x and x < log2(N+1) + k*log2(10)

With these "equations" and brute-forcing on k we can found x fast enough.

(May be I've missed something, sorry, I've solved this one a long time ago).

Well with these equations we can find that E or x lies between a certain range.
But how can we select a particular value of E within this range. I m sorry but i m not completely getting this point.

my code is like this in this code

Code: Select all

void ProcessNumber(int n)
{
int k = 0, temp = n;
double  min = 0, max = 0;
      
      while (temp > 0) {
         temp /= 10;
         ++k;
      }
      
      k+= 1;
      
      for (k; k < INT_MAX; ++k) {

         min = (log10(n) + k) / log10(2);
         max = (log10(n + 1) + k) / log10(2);
 /* this is the minium and maxmim range for E  but how can i choose a  particular E */
                         

      }
      
}

[phoenix7]

can any one answer what the range of output is?

[ranban282]

I'm following the log approach as suggest. Can anyone tell me what is wrong, or why i'm getting floating point errors?
Here's the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;
int n_digits(int n)
{
   int i=0;
   while(n>=10)
   {
      n/=10;
      i++;
   }
return i;
}
int main()
{
   
   unsigned int  n;
   long double lg=log((long double)10.0)/log((long double)2.0),lg2=log((long double)2.0);
   while(cin>>n)
   {
      int i=n_digits(n);
      for(long double j=i+2.0;;j++)
      {
         if(ceil(log((long double)n)/lg2+j*lg)==floor(log((long double)n+1.0)/lg2+j*lg))
         {
            printf("%.0Lf\n",ceil(log((long double)n)/lg2+j*lg));
            break;
         }
      }   
   }   
   return 0;
}


[ranban282]

Hi,
I changed everything to long double as suggested. Can anyone tell me the error in my code? If anyone has got AC can they post or mail me the code?
If you could have a look at my code and tell me whether it is a logical error or a precision error, I would be infinitely grateful to you.
Here's the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;
long double n_digits(long double n)
{
   long double i=0.0;
   while(n>=10.0)
   {
      n/=10.0;
      i+=1.0;
   }
return i;
}
int main()
{
   
   long double  n;
   while(cin>>n)
   {
      long double i=n_digits(n);
      for(long double j=i+2.0;;j+=1.0)
      {
         long double arg1= n;
         long double arg2=n+1.0;
         long double log2=log10(2.0);
         if(ceil((log10(arg1)+j)/log2)==floor((log10(arg2)+j)/log2))
         {
            printf("%.0Lf\n",ceil((log10(arg1)+j)/log2));
            break;
         }
      }   
   }   
   return 0;
}


[ranban282]

WHAT IS THE PROBLEM WITH MY CODE? WHY DO I GET WA?????
EITHER GIVE ME TEST CASES FOR WHICH I GET WA OR HOW TO ELIMINATE PRECISION ERROR?

here's the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;


int main()
{
   
   long double  n;
   while(cin>>n)
   {
      long double i=floor(log10(n));
      long double log2=log10((long double)2.0);
      for(long double j=i+2.0;;j+=1.0)
      {
         long double arg1= n;
         long double arg2=n+1.0;
         
         
         if(ceil((log10(arg1)+j)/log2)==floor((log10(arg2)+j)/log2))
         {
            printf("%.0Lf\n",ceil((log10(arg1)+j)/log2));
            break;
         }
      }   
   }   
   return 0;
}



[vahid sanei]

I got time limit for this tescase n = 2147483647
but i got Acc
could you help me for solving this test case ?
(" I know we can`t prove that "n is`nt a part of power of 2" because of numbers are infinity so we should`nt print "no power of 2"
Thanks in advance

[vahid sanei]

to ranban
I got Acc with your code
you can use ceill instead of ceil

[DD]

I think there will be an answer for this problem so it means we don't need to print "no power of 2".