← 返回题目列表

AtCoder · fuka_sugoroku

E. 双六

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

说明

F 正在尝试使用一个六面骰子独自玩双六。

在双六方格中,有两个选项:“前进○方格”和“回到起点”,如果你停在那里,你必须始终按照指示移动。如果您由于方块的效果而移动并最终停在再次具有该效果的方块处,请按照指示继续移动。

由于F很慢,所以实际玩双六变得很痛苦。因此,我们决定找到达到目标的掷骰子次数的期望值。

输入

输入由多个测试用例组成。输入的结尾由仅包含一个零的行表示。每个测试用例均按以下格式给出。

n
x_1 x_2 … x_n
  • 1≦n≦500,000
  • -1≦x_i≦n-i
  • x_1,x_n=0

测试用例1双六中的方格数显示在行中 写入n。对于鳟鱼 它的编号最大为1与n。起始正方形是1,然后按最接近开始的顺序排列。2番,3番,…,n-1目标方块继续。 号码是n。i在编号的方块上掷骰子 如果你投掷j, 移至方块i+j。如果 如果分数为i+j是 在n或更高,则视为已达到目标。 在

测试用例2行中,n整数 写入x_i。 代表写在第x_i是 它仅由i个方格中的指令。x_i = -1 然后,“回到开头。”0 < x_i ≦ n-i 然后“x_i继续前进”,x_i = 0 那么对该方格没有影响。

x_1, x_n 是 它仅由0有保证。给定的双六有可能达到目标,掷骰子次数的期望值为 保证该值不会超过10^7。每个文件的测试用例数量保证不超过300个。另外,对于每个文件n的总和保证小于或等于 500,000。

输出

对于每个测试用例,在一行上打印预期的骰子数量。该误差可以是绝对误差或相对误差。10^{-7}。

示例输入

2
0 0
7
0 -1 -1 -1 -1 -1 0
7
0 0 0 0 0 0 0
7
0 5 4 3 2 1 0
8
0 -1 -1 -1 0 -1 -1 0
0

示例输出 由

1.00000000
6.00000000
2.16139403
1.00000000
10.50000000