11666 - Logarithms

[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.

[SRX]

input:

Code: Select all

9
8
7
0

9

output

Code: Select all

2 -0.21801755
2 -0.08268227
2 0.05265302

notice that -1<x<1

[dodouuu]

You help me a lot ^^ thank you very much

[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.

[dodouuu]

I think this problem asks for this:

for(l=floor(logn); ; l++){
x = 1-exp(logn-l);
if( fabs(x)<1+eps )return;
}

[lgarcia]

I solved the problem with this:

Code: Select all

L = ceil(log(n) - log(2.));
x = 1 - exp(log(n) - L);

[apurba]

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

Code: Select all

L=ceil(lon(n) - log(2.0));

log(2.0) here????

[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

Code: Select all

L = floor(log(n) - log(2.) + 1.);

[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]

[ymgve]

Is this even possible to do in Java? I just get TLE:

Code: Select all

accepted

[stubbscroll]

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

[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.

[arifcsecu]

Accepted

Thanks

[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.

[arifcsecu]

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 ?