← 返回题目列表

Codeforces · 1245/E

E. 百极和梯子

中文机器翻译题面 查看原题

百极刚刚从南黑螺寺的住神退休,以追求成为漫画家的梦想。她在那座寺庙里呆了六个月,只是玩“猫的摇篮”,所以现在她想尝试一种不同的游戏——“蛇和梯子”。可惜她已经把蛇都杀光了,所以现在只剩下梯子了。

游戏在 $$$10 \times 10$$$ 棋盘上进行,如下所示:

- 游戏开始时,玩家位于左下方的方块中。
- 游戏的目标是玩家通过沿着路径攀爬垂直梯子来达到目标​​(左上角的方块)。一旦玩家达到目标,游戏就结束。
- 路径如下:如果一个方格不是其所在行的末尾,则沿其所在行的方向通向其旁边的方格;如果一个方格是其行的末尾,则它通向其上方的方格。行的方向确定如下:最底行的方向为向右;任何其他行的方向与其下方行的方向相反。请参阅注释部分以了解路径的可视化。
- 在每个回合中,玩家掷一个标准的六面骰子。假设骰子上显示的数字是$$$r$$$。如果目标小于路径上的 $$$r$$$ 方格,则玩家不会移动(但会执行回合)。否则,玩家将沿着路径前进 $$$r$$$ 格,然后停止。如果玩家停在梯子底部的方格上,则玩家可以选择是否爬上梯子。如果她选择不攀爬,那么她会留在该方块中等待下一个回合的开始。
- 有些方块里有一个梯子。梯子仅垂直放置——每个梯子都通向上面几排的同一个正方形。为了让玩家爬上梯子,在掷骰子后,她必须停在包含梯子底部的方格处。使用梯子后,玩家将最终到达包含梯子顶部的正方形。她不能在攀登过程中离开梯子。如果包含梯子顶部的正方形也包含另一个梯子的底部,则不允许她使用第二个梯子。
- 骰子面上的数字为 1、2、3、4、5 和 6,每个数字出现的概率相同。

请注意:

- 梯子有可能重叠,但玩家在攀登第一个梯子的过程中无法切换到另一个梯子;
- 梯子可以直接到达顶行,但不能再更高;
- 两个梯子有可能通向同一个图块;
- 梯子有可能通向也有梯子的图块,但如果玩家使用第一个梯子,她将无法使用第二个梯子;
- 玩家只能爬上梯子,不能爬下来。

百极想要尽快结束游戏。因此,在每个回合中,她都会选择是否以最佳方式爬上梯子。帮助她确定游戏所需的最少预期回合数。

输入

输入将由十行组成。第 $$$i$$$ 行将包含 10 个非负整数 $$$h_{i1}, h_{i2}, \dots, h_{i10}$$$。如果 $$$h_{ij}$$$ 为 $$$0$$$,则第 $$$i$$$ 行和 $$$j$$$ 第 $$$j$$$ 列的图块没有梯子。否则,该图块处的梯子的高度将为 $$$h_{ij}$$$,即攀爬梯子将通向正上方的图块 $$$h_{ij}$$$ 行。保证 $$$0 \leq h_{ij} < i$$$。此外,第一行的第一个数字和最后一行的第一个数字始终包含 $$$0$$$,即目标和起始图块永远不会有梯子。

输出

仅打印包含单个浮点数的一行——百极完成游戏所需的最小预期轮数。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

示例

输入 #1

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

输出 #1

33.0476190476

输入 #2

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 4 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 9

输出 #2

20.2591405923

输入 #3

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

输出 #3

15.9047592939

注意

示例 2 中的路径和棋盘的可视化如下:

带有“S”的图块是起始图块,带有“E”的图块是目标。

对于第一个示例,没有梯子。

对于第二个示例,该板看起来类似于图像右侧部分的板(为了清晰起见,梯子已着色)。

梯子可能会重叠,例如红色和黄色梯子以及绿色和蓝色梯子的情况。梯子也可以直接到达顶部,就像黑色和蓝色梯子的情况一样。然而,梯子不可能走得更高(在棋盘之外)。两个梯子也可能通向同一个图块,就像红色和黄色梯子的情况一样。另外,请注意红色和黄色的梯子通向带有橙色梯子的图块。因此,如果玩家选择爬红色和黄色梯子中的任何一个,他们将无法爬橙色梯子。最后,请注意绿色梯子穿过蓝色梯子的起始图块。玩家在爬绿色梯子的过程中不能从绿色梯子转移到蓝色梯子。