ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1631. Drunk King 2

Time limit: 1.0 second
Memory limit: 64 MB
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 of mn.
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 requirements:
  • King starts and finishes the traversal in a corner of the board.
  • Every cell except for the first one is visited exactly once.
  • King 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 wrong way).


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 guaranteed.


7 7


Below is an example of a shortest traversal of the 7 × 7 chess board satisfying the conditions of the problem:
Problem illustration
Problem Author: Igor Chevdar
Problem Source: XIII Open USU Championship