Page 1 of 2
11666 - Logarithms
Posted: Mon Sep 14, 2009 4:48 pm
by dodouuu
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
Posted: Mon Sep 14, 2009 5:08 pm
by SRX
input:
9
output
Code: Select all
2 -0.21801755
2 -0.08268227
2 0.05265302
notice that -1<x<1
Re: 11666 Logarithms WA again and agian
Posted: Mon Sep 14, 2009 5:21 pm
by dodouuu
You help me a lot ^^ thank you very much
Re: 11666 Logarithms WA again and agian
Posted: Mon Sep 14, 2009 5:54 pm
by fushar
Rearranging terms gives us
ln(n)-L = ln(1-x) ; -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
Posted: Mon Sep 14, 2009 6:08 pm
by dodouuu
I think this problem asks for this:
for(l=floor(logn); ; l++){
x = 1-exp(logn-l);
if( fabs(x)<1+eps )return;
}
Re: 11666 Logarithms WA again and agian
Posted: Mon Sep 14, 2009 7:51 pm
by lgarcia
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
Posted: Mon Sep 14, 2009 9:36 pm
by apurba
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????
Re: 11666 Logarithms WA again and agian
Posted: Mon Sep 14, 2009 10:18 pm
by lgarcia
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
Re: 11666 Logarithms WA again and agian
Posted: Wed Sep 16, 2009 10:33 am
by noor_aub
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
Posted: Thu Sep 24, 2009 6:31 pm
by ymgve
Is this even possible to do in Java? I just get TLE:
Re: 11666 Logarithms WA again and agian
Posted: Thu Sep 24, 2009 9:31 pm
by stubbscroll
ymgve wrote:Is this even possible to do in Java? I just get TLE:
You probably get TLE because there are a lof of test cases, and hence a lot of output. Try buffering the output, for instance:
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
Posted: Fri Sep 25, 2009 9:32 am
by ymgve
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.
Re: 11666 Logarithms WA again and agian
Posted: Fri Sep 25, 2009 11:38 am
by arifcsecu
Accepted
Thanks
Re: 11666 Logarithms WA again and agian
Posted: Mon Oct 05, 2009 6:51 am
by calicratis19
my ac code gives,
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
you can visit here
http://www.uvatoolkit.com/problemssolve.php to generate test case.
hope it helps.
Re: Replica Mulberry Handbags
Posted: Fri Nov 13, 2009 3:30 pm
by arifcsecu
abcd264 wrote:Mulberry was founded in 1971 by Roger Saul through a gift of 50-pounds 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 ?