← 返回题目列表

AtCoder · jag2017summer_day1_c

C. 双六

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

問題文

黑猫斯努克正在和双六玩耍。

这个双六使用了不寻常的骰子。 这个骰子已经全部 有 N 张面孔,每张面孔出现的概率相同。 第 i 面是一个整数。 写着 A_i ,当这一面出现时,将棋子准确移动。 A_i 前进。

另一方面,这个双六中使用的方块并不是那么不寻常。 总共 M 方块排成一排,1 第格开始,M 第一个方格是目标。 i 是一个整数 如果写入 B_i 并且停在这个方块上, B_i 的值具有以下效果。

  • B_i 是 0 或更多:精确移动棋子 B_i 前进。但前进的空间效果不会受到影响。 如果小于
  • B_i 是 0 :-B_i 关闭。

现在,Snuke 使用双六到达目标需要多少回合?

此外,在这个双六中,如果你试图超越目标,它也会被视为一个目标。

制約

  • 1≦N≦10^5
  • 2≦M≦10^5
  • 1≦A_i≦M
  • -10≦B_i≦M
  • B_1=B_M=0

入力

输入是按以下格式从标准输入给出的。

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M

出力

输出到达目标所需的预计圈数。 然而,如果绝对或相对误差 10^{-4} 如果答案如下,则视为正确。


入力例 1

3 4
1 2 3
0 1 -1 0

出力例 1

2.00000000000000000000

考虑到第一回合的每次掷骰,如下所示。

  • 突出的眼睛 对于 1 :1 前进, 它停在第2 个方格。由于该质量的影响, 前往第3 个方格。在下一个回合,无论你掷什么,你都可以得分,所以总数将为 2 需要转弯。
  • 突出的眼睛 对于 2 :2 前进, 它停在第3 个方格。由于该质量的影响, 前往第1 关闭。下个回合是假期,下个回合无论你掷什么都可以得分,所以目标总共包括 它停在第 3 需要转弯。
  • 突出的眼睛 对于 3 :3 前进, 它停在第4 个方格。也就是说,1 你可以在一个回合内达到目标。

因此,期望值为 2/3 + 3/3 + 1/3 = 2 变为。


入力例 2

1 10
1
0 0 0 0 0 0 0 0 0 0

出力例 2

9.00000000000000177636

入力例 3

5 6
1 1 2 3 5
0 0 6 -10 1 0

出力例 3

4.47999999999999953815