Once upon a time King, Knight, and Bishop met each other on an
m × n chess board with odd lengths of sides. They
started speaking about traversals of the chess board. It turned out that each
of them had always been unlucky in this. Bishop complained that he couldn't
traverse the board visiting every cells exactly once because he was allowed to
step only on cells of the same color. Knight said that he could visit all cells
but couldn't do it in such a way as to return to the cell from which he had
started. And King said that he could traverse the board but the dream of his
life had always been to find a closed traversal with a length
Out of grief, the three friends drank and then continued their talk. King
said that recently he had found a closed
(mn − 1 + √2) long traversal. Knight and
Bishop started laughing at him: “You're drunk now! You can't traverse it
at all!” Indeed, King was so drunk that he couldn't make two consecutive
moves in the same direction. However, King traversed the board in front of
their very eyes. Moreover, he said that the traversal was the shortest one.
To be sure that King hadn't cheated, Bishop and Knight wanted to know the
length of the shortest traversal of the drunk King. They couldn't calculate
this length, being drunk themselves, so they asked you to help them.
Remember that a traversal of the board must satisfy the following
- King starts and finishes the traversal in a corner of the board.
- Every cell except for the first one is visited exactly once.
can't make two consecutive moves in the same direction.
- King is not
allowed to cross his own route (otherwise, he may get confused and walk the
The only input line contains the odd integers m
and n (6 < m, n < 500).
Output the length of the shortest traversal of the drunk
King accurate to 10−9. The existence of such a traversal is
Below is an example of a shortest traversal of the 7 × 7 chess
board satisfying the conditions of the problem:
Problem Author: Igor Chevdar
Problem Source: XIII Open USU Championship