Editorial for SAC '22 Code Challenge 3 P2 - Unicycle License - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 3 P2 - Unicycle License

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.

Author: maxcruickshanks

The equation that needs to be solved is $12t^2 - 5t + 1 = M$ ~12t^2 - 5t + 1 = M~, which can be rearranged to $12t^2 - 5t + 1 - M = 0$ ~12t^2 - 5t + 1 - M = 0~.

Next, solve the equation using the quadratic formula and take the positive solution.

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Alternative Solution

Binary search for the first point with a solution larger than $M$ ~M~ and up to a precision of $10^{-6}$ ~10^{-6}~.

Time Complexity: $\mathcal{O}(\lceil\log(10^{9 + 6})\rceil)$

Comments

There are no comments at the moment.