701 - The Archeologists' Dilemma

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

problem 701

Post by temper_3243 » Sun Oct 23, 2005 11:37 am

Hi,
This is about problem 701 (Archaeologists dilemma).
http://acm.uva.es/p/v7/701.html


If i am given k digits of a number and the missing digits n-k > k , how do i find the smallest exponent x such that first k digits of 2^x =k . I have been trying out an algorithm but couldn't find one. I had searched the forum but no algorithms are present only sample inputs and outputs.

Can someone help me out or explain me how to solve this problem fast ?

Regards
Terry

User avatar
brunokbcao
New poster
Posts: 4
Joined: Sun May 14, 2006 4:22 pm
Location: Recife, PE
Contact:

Post by brunokbcao » Mon Jul 03, 2006 11:16 pm

Thanks... I was using strings :oops:

atif_ilm
New poster
Posts: 1
Joined: Mon Aug 07, 2006 5:15 pm
Contact:

Post by atif_ilm » Mon Aug 07, 2006 5:25 pm

Ivan Golubev wrote: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
New poster
Posts: 5
Joined: Fri Oct 07, 2005 11:21 pm
Location: Tehran, IRAN
Contact:

Post by phoenix7 » Tue Sep 12, 2006 11:40 am

can any one answer what the range of output is?
-- Mohammad
do you Python?

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

WHY WA???

Post by ranban282 » Tue Sep 12, 2006 7:45 pm

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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

THIS PROBLEM IS DRIVING ME NUTS!

Post by ranban282 » Thu Sep 14, 2006 11:07 pm

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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

I WILL KEEP POSTING UNTIL I GET AC

Post by ranban282 » Mon Oct 09, 2006 12:35 am

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;
}


User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 701 - The Archeologists' Dilemma

Post by vahid sanei » Sat Feb 14, 2009 5:05 pm

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 :wink:
Impossible says I`m possible

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 701 - The Archeologists' Dilemma

Post by vahid sanei » Sat Feb 14, 2009 5:46 pm

to ranban
I got Acc with your code
you can use ceill instead of ceil
Impossible says I`m possible

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 701 - The Archeologists' Dilemma

Post by DD » Sun Feb 24, 2013 8:48 pm

I think there will be an answer for this problem so it means we don't need to print "no power of 2".
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

metaflow
New poster
Posts: 2
Joined: Fri May 23, 2014 7:47 pm

Re: 701 - The Archeologists' Dilemma

Post by metaflow » Sun Sep 21, 2014 3:46 pm

It look like there are a lot of inputs that leads to "no power of 2" answer that is valid. Try 309305843 for example.
I have no formal proof but I have checked that if we take in account only 8 first digits then set of possible prefixes of numbers is significantly less than 10^8-1 (at 2^6432187 = 16777216.. new cycle starts)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 701 - The Archeologists' Dilemma

Post by brianfry713 » Tue Sep 23, 2014 2:15 am

You can get AC on the judge for this problem without ever printing "no power of 2", so the judge's input doesn't contain cases like this.

Can you provide a proof or your code that you used to come up with the cycle length? Why did you only take into account the first 8 digits when N can be up to 10 digits long?
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 701 - The Archeologists' Dilemma

Post by brianfry713 » Tue Sep 23, 2014 6:39 am

http://math.stackexchange.com/questions ... le-numbers

There are no cases where you should print no power of two, but some inputs may require a large output and take some time to run.
Check input and AC output for thousands of problems on uDebug!

Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

Re: 701 - The Archeologists' Dilemma

Post by Zwergesel » Mon Aug 01, 2016 11:38 pm

This problem seems to work only because there are no tricky judge inputs. :-?

Can someone give, for example, the answer for the input 2147333666?

Post Reply

Return to “Volume 7 (700-799)”