31955번 - Manhattan Walk 스페셜 저지다국어

문제

It's a grid system! You begin at the top left corner and want to walk to the bottom right corner. Every location is at integer coordinates, and has an arrow pointing down or right and a timer that, every few seconds, flips the arrow from down to right, or from right to down. When you begin your walk, every arrow is pointing down or right with equal probability, and every timer has a real value chosen uniformly in the range from zero to its maximum wait time.

At any moment in time, if you are at a given location, you can:

• Move down one location if the new location is on the grid and the arrow is pointing down.
• Move right one location if the new location is on the grid and the arrow is pointing right.
• Wait for the timer to finish its countdown so that the arrow flips from down to right, or from right to down.

When you arrive at a new location, you are able to see the timer and can therefore take that into account when deciding which action to take. However, you are not able to look ahead---you can only see the timer and arrow for the exact grid point you occupy. You hate waiting, and want to minimize the total amount of time you're waiting for an arrow to flip.

What is the expected amount of time you have to wait if you make decisions optimally?

입력

The single line of input contains three integers $r,ドル $c$ (1ドル \leq r, c \leq 10^3$), and $p$ (1ドル \leq p \leq 10^9$), where $r$ is the number of rows in the grid, $c$ is the number of columns in the grid, and $p$ is the maximum value a timer can show.

출력

Output a single number, which is the expected time you have to wait if you make optimal decisions. Your answer will be accepted if the absolute or relative error is within 10ドル^{-6}$ of the judge's answer.

제한

힌트