#P8213. [THUPC2022 初赛] 挑战
[THUPC2022 初赛] 挑战
题目描述
足够聪明的 Alice 和 Bob 在玩一种棋盘游戏。这个游戏需要用到一个有 个格子的长条棋盘,按从左到右的顺序给每个格子编号 。除了编号为 的格以外,每一格都有两个数 。游戏开始前,将一个棋子放在第 格。游戏由二人轮流操作,这里我们不妨假设 Alice 先手。
轮到其中一位玩家进行操作时,这位玩家可以根据当前格子的 值决定前进的步数。具体地说,假设当前棋子位于第 格,那么当前进行操作的玩家可以将棋子向前移动 格,其中 可以是满足 的任意整数。如果玩家没有走满 格,即 ,那么该玩家可以在完成移动后选择是否进行一次挑战。如果选择不进行挑战,那么由另一位玩家进行下一轮操作。否则,如果当前玩家选择挑战,那么系统将会产生两个随机整数 和 ,其中: 表示挑战的能量,它在 中等概率产生; 表示挑战所需的活化能,它在 中等概率产生。根据 和 的值,系统会根据以下规则自动判定挑战结果:
如果 ,则挑战成功,对方玩家的操作被跳过一轮,由当前玩家继续操作; 如果 ,则挑战结果为平手,什么事情都不会发生,由对方玩家进行操作; 如果 ,则挑战失败,当前玩家下一轮操作将会被跳过,即对方玩家可以连续操作两轮。 为了防止其中一方玩家一直被跳过,规定:
如果当前玩家通过自身的挑战获得额外操作机会,则该玩家在该额外操作机会中不能进行第二次挑战; 如果当前玩家通过对方玩家的挑战获得额外操作机会,则该玩家不能在其第一次操作结束时发起挑战,只能在第二次操作结束时选择是否进行挑战,并且当且仅当挑战成功时可以进行第三次操作。 需要注意的是,无论连续进行多少次操作,每次操作都需要将棋子向前移动至少 格。同大多数游戏一样,谁将棋子移动到终点(即编号为 的格)谁就获胜。
Alice 和 Bob 都足够聪明,可以心算出对于当前棋子的位置,能使自己获胜概率最大的操作。作为一名旁观者,你没有他们那么强的心算能力;但是你也想通过自己编程的能力,计算出当 Alice 先手从第 格开始进行操作时,Alice 的胜率。
输入格式
输入的第一行包含一个正整数 ,表示棋盘包含 格,分别标号 。
输入的第二行包含 个正整数 ,分别表示第 格至第 格的 值。
输入的第三行包含 个正整数 ,分别表示第 格至第 格的 值。
输出格式
输出一个实数,表示 Alice 先手开始游戏的胜率。当你的输出与标准输出的绝对误差不超过 时,我们认为你的输出是正确的。
3
3 3 3
1 2 3
1.000000000000000000
3
2 3 3
1 2 3
0.250000000000000000
10
2 1 4 7 4 8 3 6 4 8
3 1 4 1 5 9 2 6 5 3
0.833333333333333333
提示
【样例解释 1】
Alice 先手,由于可以直接从第 格移动到终点的第 格,Alice 会直接将棋子移动到第 格,故 Alice 必胜。
【样例解释 2】
Alice 先手,但是不能直接移动到第 格,并且无论结束操作时棋子在第 格还是第 格,Bob 都可以直接将其移动到终点的第 格,因此 Alice 必须尝试挑战。将棋子移动到第 格并发动挑战,挑战成功的概率为 ,故 Alice 的胜率为 。
【数据范围】
对于 的数据,保证 ,。