import java.util.*; /** * Dynamic programming submission. * At each step either follow the arrow immediately or wait for the arrow to flip. * Whether it is a better to wait or not is dependent on the value of the timer * when the cell is arrived at. * * @author Finn Lidbetter */ public class finn_walk { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); long p = sc.nextInt(); Double[][] dp = new Double[n][m]; dp[n-1][m-1] = 0.0; System.out.println(solve(0,0,dp, p)); } static double solve(int row, int col, Double[][] dp, double p) { if (dp[row][col] != null) { return dp[row][col]; } // arrowDown is the expected time to complete the walk if we arrive and the arrow is pointing down. double arrowDown = 0; // arrowRight is the expected time to complete the walk if we arrive and the arrow is pointing right. double arrowRight = 0; if (row==dp.length-1) { // We must go right. // Wait for the arrow to flip. arrowDown = p/2.0 + solve(row, col+1, dp, p); // Follow the arrow immediately. arrowRight = solve(row, col+1, dp, p); } else if (col==dp[0].length-1) { // We must go down. // Follow the arrow immediately. arrowDown = solve(row+1, col, dp, p); // Wait for the arrow to flip. arrowRight = p/2.0 + solve(row+1, col, dp, p); } else { double right = solve(row, col+1, dp, p); double down = solve(row+1, col, dp, p); if (right >= down) { // Down is better. arrowDown = down; // We can either follow it immediately or wait for the arrow to flip. double cappedDiff = Math.min(right - down, p); // If the arrow is pointing right and the timer is too big, it is best to go right immediately. arrowRight += ((p-cappedDiff)/p) * right; // If the arrow is pointing right and the timer is small enough, then wait to go down. arrowRight += (cappedDiff/p) * (cappedDiff/2.0 + down); } else { // Right is better. arrowRight = right; double cappedDiff = Math.min(down - right, p); // If the arrow is pointing down and the time is too big, it is best to go down immediately. arrowDown += ((p-cappedDiff)/p) * down; // If the arrow is pointing down and the timer is small enough, then wait to go right. arrowDown += (cappedDiff/p) * (cappedDiff/2.0 + right); } } dp[row][col] = arrowDown/2.0 + arrowRight/2.0; return dp[row][col]; } }