Editorial for TLE '15 P4 - Olympiads Homework

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Using the pow() method will earn 10% of the points.

Additionally, doubles are imprecise and will give incorrect answers. Thus, they must be avoided for this problem.

To earn all of the points, we must use the quick power algorithm to quickly and accurately get exponent results. One can also realize that $\sqrt{2}^{2k} = 2^k$ ~\sqrt{2}^{2k} = 2^k~. If the exponent is odd, then the cosine function will produce a $\sqrt{2}$ ~\sqrt{2}~, which will even out the other $\sqrt{2}$ ~\sqrt{2}~.

The only corner case is $N = 1$ ~N = 1~, which is $\frac{1}{2}+\frac{1}{2} = 1$ ~\frac{1}{2}+\frac{1}{2} = 1~ according to the formula.

Time complexity: $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~

Comments

There are no comments at the moment.