410558: GYM104049 J Knight In Shining Armor 1

Note that this is problem is an easier version of Knight in Shining Armor 2. There are significant differences between the two problems, so please read both carefully.

Charles is a chess prodigy, but his parents are worried that he spends too much time indoors. So, they have decided to create an exercise for him that will allow him to train his chess skills while also getting some vitamin D. Charles's parents have drawn an $$$N \times N$$$ chess board using chalk and provided Charles with a giant knight chess piece made out of tungsten. To keep him busy for a while, his parents tell him to place the knight on a certain square of the board and then repeatedly make knight moves until the knight ends up back on the square it started. Charles is a really indecisive chess player, so at each step, he will choose uniformly randomly from the legal moves available for his knight (note that there will always be at least one legal move, and that Charles will never move the knight off of the board).

Since the knight is made of tungsten, its quite heavy, and Charles would like to be done as soon as possible. At the very least, he would like some kind of estimate as to when he will be done moving the knight. Since he isn't great with mathematics, he's tasked you with coming up with this value. Given the starting square and the board size, please report back to Charles with the expected number of knight moves he will have to make before he ends up back where he started on the chess board.

The only line of input will consist of three space-separated integers, $$$N\ (8 \leq N \leq 20)$$$, $$$X\ (0 \leq X < N)$$$, and $$$Y\ (0 \leq Y < N)$$$ denoting the board size ($$$N \times N$$$) as well as the starting square ($$$(X, Y)$$$, where $$$X$$$ denotes the $$$X$$$-th row from the top and $$$Y$$$ denotes the $$$Y$$$-th column from the left).

Your output should consist of a single floating point number denoting the expected number of knight moves that Charles will have to make until the knight reaches the starting square again. Your answer will be correct if it has absolute error less than or equal to $$$10^{-9}$$$.

8 0 0

168.000000000000