11666  Logarithms
Moderator: Board moderators
11666  Logarithms
I got wrong answer again and again during the contest yesterday. And today, I got wrong answers all day.... Please tell me how to solve this problem. I will appreciate you very much.
Re: 11666 Logarithms WA again and agian
input:
9
output
notice that 1<x<1
Code: Select all
9
8
7
0
output
Code: Select all
2 0.21801755
2 0.08268227
2 0.05265302
studying @ ntu csie
Re: 11666 Logarithms WA again and agian
You help me a lot ^^ thank you very much
Re: 11666 Logarithms WA again and agian
Rearranging terms gives us
ln(n)L = ln(1x) ; 1 < x < 1
So this problem asks for smallest L such that 0 < e^(ln(n)L) < 2.
That can be accomplished using binary search on L.
I haven't got AC, though.
ln(n)L = ln(1x) ; 1 < x < 1
So this problem asks for smallest L such that 0 < e^(ln(n)L) < 2.
That can be accomplished using binary search on L.
I haven't got AC, though.
Re: 11666 Logarithms WA again and agian
I think this problem asks for this:
for(l=floor(logn); ; l++){
x = 1exp(lognl);
if( fabs(x)<1+eps )return;
}
for(l=floor(logn); ; l++){
x = 1exp(lognl);
if( fabs(x)<1+eps )return;
}
Re: 11666 Logarithms WA again and agian
I solved the problem with this:
Code: Select all
L = ceil(log(n)  log(2.));
x = 1  exp(log(n)  L);
Re: 11666 Logarithms WA again and agian
lgarcia wrote:I solved the problem with this:Code: Select all
L = ceil(log(n)  log(2.)); x = 1  exp(log(n)  L);
hi, lgarcia
can you please make it clear to me, why you use
log(2.0) here????Code: Select all
L=ceil(lon(n)  log(2.0));
Code: Select all
keep dreaming...
Re: 11666 Logarithms WA again and agian
I'm sorry, I should be more clear.
We get this from the problem,
ln(n) = L + ln(1  x) => n = e^L * (1  x)
Also we have this,
x < 1 => 1 < x < 1 => 0 < 1  x < 2
Then,
e^L * (1  x) < 2 * e^L => n < 2 * e^L => ln(n) < ln(2) + L => ln(n)  ln(2) < L
Since we don't get (or I didn't see) any other constraint, L is just the lowest integer greater than ln(n)  ln(2).
Actually my solution is wrong if ln(n)  ln(2) is an integer, however my solution was accepted.
The right one (also accepted) should be
We get this from the problem,
ln(n) = L + ln(1  x) => n = e^L * (1  x)
Also we have this,
x < 1 => 1 < x < 1 => 0 < 1  x < 2
Then,
e^L * (1  x) < 2 * e^L => n < 2 * e^L => ln(n) < ln(2) + L => ln(n)  ln(2) < L
Since we don't get (or I didn't see) any other constraint, L is just the lowest integer greater than ln(n)  ln(2).
Actually my solution is wrong if ln(n)  ln(2) is an integer, however my solution was accepted.
The right one (also accepted) should be
Code: Select all
L = floor(log(n)  log(2.) + 1.);
Re: 11666 Logarithms WA again and agian
Any body help me to solve the problem. I am getting wrong answer.
Code: Select all
l=floor(log(n)/log(2));
x = 1  exp(log(n)  l);
[\Code]
Re: 11666 Logarithms WA again and agian
Is this even possible to do in Java? I just get TLE:
Code: Select all
accepted
Last edited by ymgve on Fri Sep 25, 2009 9:25 am, edited 1 time in total.

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
Re: 11666 Logarithms WA again and agian
You probably get TLE because there are a lof of test cases, and hence a lot of output. Try buffering the output, for instance:ymgve wrote:Is this even possible to do in Java? I just get TLE:
Code: Select all
StringBuffer bf=new StringBuffer();
// calculate answer
bf.append(answer);
// print all output
System.out.print(bf);
Re: 11666 Logarithms WA again and agian
Yeah, StringBuffer did the trick. But I feel the time limit is still too close. The largest problem seems to be that formatting strings in Java is quite slow, and there is no easy way of achieving the same combination of rounding and number of decimals as String.format(). It would be more ideal if the task just said "correct to 8 decimal places", but I don't know if the judge is capable of checking that. I assume it basically diffs the answer output with the correct one.

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
Re: 11666 Logarithms WA again and agian
Accepted
Thanks
Thanks
Last edited by arifcsecu on Mon Oct 05, 2009 7:53 am, edited 1 time in total.
Try to catch fish rather than asking for some fishes.

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
Re: 11666 Logarithms WA again and agian
my ac code gives,
you can visit here http://www.uvatoolkit.com/problemssolve.php to generate test case.
hope it helps.
Code: Select all
0 0.00000000
1 0.26424112
1 0.10363832
1 0.47151776
1 0.83939721
2 0.18798830
2 0.05265302
2 0.08268227
2 0.21801755
2 0.35335283
2 0.48868812
2 0.62402340
4 0.83156389
5 0.34758940
6 0.25637435
9 0.23409804
12 0.26269452
16 0.12535175
21 0.24174396
hope it helps.
Heal The World

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
Re: Replica Mulberry Handbags
abcd264 wrote:Mulberry was founded in 1971 by Roger Saul through a gift of 50pounds sterling from his mother Joan. Roger began by selling his own designs for leather chokers and belts to such high fashion shops as Biba in London. His first collection of belts in suede and leather demonstrated the influence of saddlery techniques and traditional English crafts, and were worked to Saul's designs by local craftsmen housed in what was once an old forge in his parent's garden in Chilcompton, near Bath. The following year Saul made Mulberry's first significant export an order of a thousand belts from the Paris department store Au Printemps, while Saul created a subsequent belt collection for Jean Muir. By 1975 Mulberry had expanded into Europe, with handbag designs for Kenzo in Paris and a special range for Bloomingdale's in New York. Replica Mulberry Handbags
WHAT IS THIS ?
Try to catch fish rather than asking for some fishes.