Codeforces 362 E

okay
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
^ explicit formula for fibonacci
so
if you draw a pretty little tree diagram
you know that after the first turn, it either goes to the left or the right
and then you have 3 possible positions:
middle, which goes left or right
or left and right, which can either stay or go back to the middle

so then when it's left/right, it has a 1/2 chance of going back to the middle, while middle has 0
so if you let p(n) be the probability of middle after n turns
then p(n + 1) = 1/2 (1 - p(n))
since p(n) is the # of middles, so therefore 1 - p(n) is the number of lefts + rights
then after that you can rearrange to find that 2p(n+1) + p(n) = 1
and since this is true for all n, then 2p(n) + 2p(n - 1) = 1
so then you set these equal to each other and p(n) + p(n - 1) = 2p(n+1)
which is like a pseudo fibonacci
and you can guess that the explicit formula for p(n) is something close to c * x ^ n
where c and x are constants
so then you end up with the equation c * x ^ n + c * x ^ (n - 1) = 2 * c * x ^ (n + 1)
and you can cancel and get the quadratic 2 x^2 - x - 1 = 0
and this has roots 1 and -1/2
so i stole some inspiration from the fibonacci formula and tried to put it in the form (1) ^ n - (-1/2) ^n
and plugged in values of p(1) p(2) and p(3) to solve for the other constants
and that got me the 2/3 and the 1-
and you piece it all together and that's the formula