701  The Archeologists' Dilemma
Moderator: Board moderators
701  The Archeologists' Dilemma
I think I've probed that for each N in the given range, there's a power of 2 satisfied all the conditions. But for some larger N, I don't have a effective algorithm to solve it on time!
So, will anybody give me some tips of the correct algorithm?
So, will anybody give me some tips of the correct algorithm?
> suppose the prefix is a
> > a*10^n <= 2^x < (a+1)*10^n
> > a <= 2^x/10^n < a+1
> > a <= 2^m/5^n < a+1, where m=xn
> > 1 <= 2^m/5^n/a < 1+1/a
> >
> > 2^p/5^q = 1
> > plog(2) = qlog(5)
> > q/p = log(2)/log(5) = 0.43067655807339306
> > = [0, 2, 3, 9, 2, 2, ... ] in continuous
> > fraction
> > = 0/1, 1/2, 3/7, 28/65, 59/137, 146/339 ...
> > Accordingly,
> > 2^1/5^0 = 2
> > 2^2/5^1 = 0.8
> > 2^7/5^3 = 1.024
> > 2^65/2^28 = 0.9903520314283045
> > 2^137/2^59 = 1.0043362776618743
> > 2^339/5^146 = 0.9989595361011142
> >
> > Initially,
> > the ratio is 1/5^(d+1)/a < 1, where d is the # of
> > a's digits.
> > so multiply it by 2 until it's greater than 1
> > if the ratio is not in [1, 1+1/a) then
> > multiply it by 0.8 until it's less than 1+1/a
> > if the ratio is not in [1, 1+1/a) then
> > multiply it by 1.024 until it's greater than
> > 1
> > ...
> > */
> > a*10^n <= 2^x < (a+1)*10^n
> > a <= 2^x/10^n < a+1
> > a <= 2^m/5^n < a+1, where m=xn
> > 1 <= 2^m/5^n/a < 1+1/a
> >
> > 2^p/5^q = 1
> > plog(2) = qlog(5)
> > q/p = log(2)/log(5) = 0.43067655807339306
> > = [0, 2, 3, 9, 2, 2, ... ] in continuous
> > fraction
> > = 0/1, 1/2, 3/7, 28/65, 59/137, 146/339 ...
> > Accordingly,
> > 2^1/5^0 = 2
> > 2^2/5^1 = 0.8
> > 2^7/5^3 = 1.024
> > 2^65/2^28 = 0.9903520314283045
> > 2^137/2^59 = 1.0043362776618743
> > 2^339/5^146 = 0.9989595361011142
> >
> > Initially,
> > the ratio is 1/5^(d+1)/a < 1, where d is the # of
> > a's digits.
> > so multiply it by 2 until it's greater than 1
> > if the ratio is not in [1, 1+1/a) then
> > multiply it by 0.8 until it's less than 1+1/a
> > if the ratio is not in [1, 1+1/a) then
> > multiply it by 1.024 until it's greater than
> > 1
> > ...
> > */

 New poster
 Posts: 11
 Joined: Wed Oct 09, 2002 7:31 pm
 Contact:
701  how far to go?
My solution works for exponents up to 1024 (the max long double). I am getting "Wrong Answer". Is it because I need to check exponents higher then that? At what point should you stop? The question doesn't say.
Maybe there is some forumla rather then a brute force method that will give you an answer all the time, however I can't see what it would entail.
Maybe there is some forumla rather then a brute force method that will give you an answer all the time, however I can't see what it would entail.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Don't stop :D
There's been some posts on this problem. As far as I know, you have to check until you find a solution, as there is no "no power of 2". I tried using a brute force check from 0 up, and getting the first 10 or so digits using log, but still TLE. Someone once posted a method using partial fractions which I don't understand, so I can't explain that. If I remember correctly, before the "algorithms" field was taken away, people solved it using "brute force logs". I have absolutely no idea what that means...

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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 bruteforcing on k we can found x fast enough.
(May be I've missed something, sorry, I've solved this one a long time ago).
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 bruteforcing on k we can found x fast enough.
(May be I've missed something, sorry, I've solved this one a long time ago).

 New poster
 Posts: 6
 Joined: Wed Jan 22, 2003 9:19 pm
 Contact:
701
Don't we proceed in this manner :
number prefix
2^7 = 128 1
2^8 = 256 2
2^9 = 512 5
2^10 = 1024 not possible, since 1 has already been used and 10 is not less than half of the input symbols.
2^11 = 4096 4
.
.
.
2^22 = 4194304 41, 419
I did this by brute force, and still I get a WA. Can nebody help me out ? Thanx.
TheChaosHacker
number prefix
2^7 = 128 1
2^8 = 256 2
2^9 = 512 5
2^10 = 1024 not possible, since 1 has already been used and 10 is not less than half of the input symbols.
2^11 = 4096 4
.
.
.
2^22 = 4194304 41, 419
I did this by brute force, and still I get a WA. Can nebody help me out ? Thanx.
TheChaosHacker
hi Ivan,
I used your method and it works for the judge, however, some input N can still cost a long time, for example n=2147483648, or n=7654321. Which means the program can be rejected once better input is given.
if we allow x(or E) to be as big as 2^32, is there better methods?
Anyways, just some though.....
I used your method and it works for the judge, however, some input N can still cost a long time, for example n=2147483648, or n=7654321. Which means the program can be rejected once better input is given.
if we allow x(or E) to be as big as 2^32, is there better methods?
Anyways, just some though.....
"To reinforce her belief, she selects a list of numbers on which it is apparent that the number of legible digits is strictly smaller than the number of lost ones..."
You proceed in the following manner:
2^1 == 2 1
2^2 == 4 2
2^3 == 8 3
2^4 == 16 4
...
2^7 == 128 7
...
For input of '1', you must find an exponent such that 2^exponent meets two criteria:
First, the first digits of 2^exponent must match the provided digits.
Second, the number of 'missing digits' must be greater than the number of provided digits.
So, for the input '1', while 2^0 and 2^4 both provide numbers begining with 1, the number of 'missing digits' are less than or equal to the number of provided digits.
As such, you must find a power of two with 2*(number of provided digits)+1.
Hope this clarifies things.
You proceed in the following manner:
2^1 == 2 1
2^2 == 4 2
2^3 == 8 3
2^4 == 16 4
...
2^7 == 128 7
...
For input of '1', you must find an exponent such that 2^exponent meets two criteria:
First, the first digits of 2^exponent must match the provided digits.
Second, the number of 'missing digits' must be greater than the number of provided digits.
So, for the input '1', while 2^0 and 2^4 both provide numbers begining with 1, the number of 'missing digits' are less than or equal to the number of provided digits.
As such, you must find a power of two with 2*(number of provided digits)+1.
Hope this clarifies things.

 New poster
 Posts: 2
 Joined: Sun Jun 06, 2004 8:27 pm

 New poster
 Posts: 2
 Joined: Sun Jun 06, 2004 8:27 pm
Okay, Never Mind. the board rules say to only have one thread per problem, so I naturally assumed that the first thread I saw on problem 701 would be the only one; however, upon further examination of the board, I see that there are multiple threads for this problem, and that my question has already been answered. My apologies.
Please obey the rules; doing otherwise leads to this kind of confusion.

OmegaWarrior
Please obey the rules; doing otherwise leads to this kind of confusion.

OmegaWarrior
The way I understand this problem, the input number (a positive integer) is to match a power of two as follows:
1. The length of the input is "strictly" less than half the length of the power of two.
2. The first digits of the power of two are to be matched with the input.
3. The input number cannot be greater than 2147483648 (i.e. less than or equal to 2147483647).
Is this understanding correct?
1. The length of the input is "strictly" less than half the length of the power of two.
2. The first digits of the power of two are to be matched with the input.
3. The input number cannot be greater than 2147483648 (i.e. less than or equal to 2147483647).
Is this understanding correct?
Input / Output verification for Problem 701
Can someone verify this input / output ?
It consists of 16 test cases ( 16 numbers in the input ).
INPUT
OUTPUT
Peter Petrov
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:19741
It consists of 16 test cases ( 16 numbers in the input ).
INPUT
Code: Select all
1
2
3
4
10
2147
10240
9900
7200
1000000
2000000
14690
14960
10000000
100000000
500000000
OUTPUT
Code: Select all
7
8
15
12
20
31
28748
24559
4813
325147
325148
11036
37937
6432163
198096465
1578339556
Peter Petrov
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:19741
answer for 2^31 ?!
Can someone give the answer for input N = 2147483648
( that is N = 2 ^ 31 ).
Thank you in advance.
( that is N = 2 ^ 31 ).
Thank you in advance.

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact: