P16088 [ICPC 2024 NAC] Manhattan Walk

这是一个网格系统！你从左上角出发，想要走到右下角。每个位置都有整数坐标，并带有一个指向下方或右方的箭头，以及一个计时器。计时器每隔若干秒就会将箭头从向下翻转为向右，或从向右翻转为向下。在你开始行走时，每个箭头以相等的概率指向下或右，且每个计时器的初始时间均匀随机地选自 $0$ 到其最大等待时间之间。 在任何时刻，如果你位于某个位置，你可以： - 如果新位置在网格内且当前箭头指向下，则向下移动一格。 - 如果新位置在网格内且当前箭头指向右，则向右移动一格。 - 等待计时器结束倒计时，使箭头从向下翻转为向右，或从向右翻转为向下。 当你到达一个新位置时，你能够看到该位置的计时器，因此可以在决定下一步行动时将其考虑在内。然而，你不能提前预知未来的信息——你只能看到你当前所在网格点的计时器和箭头。你讨厌等待，希望最小化等待箭头翻转的总时间。 在最优决策下，你需要等待的期望时间是多少？

输入只有一行，包含三个整数 $ r $、$ c $（$ 1 \le r, c \le 10^3 $）和 $ p $（$ 1 \le p \le 10^9 $），其中 $ r $ 是网格的行数，$ c $ 是网格的列数，$ p $ 是计时器可能显示的最大值。

输出一个实数，表示在最优决策下你需要等待的期望时间。如果答案与标准答案的绝对误差或相对误差不超过 $ 10^{-6} $，则视为正确。

翻译由 DeepSeek V3.2 完成