#P8213. [THUPC2022 初赛] 挑战

    ID: 7334 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划,dp2022Special JudgeO2优化

[THUPC2022 初赛] 挑战

题目描述

足够聪明的 Alice 和 Bob 在玩一种棋盘游戏。这个游戏需要用到一个有 (n+1)(n+1) 个格子的长条棋盘,按从左到右的顺序给每个格子编号 0,1,,n0, 1, \cdots, n。除了编号为 nn 的格以外,每一格都有两个数 pi,qip_i, q_i。游戏开始前,将一个棋子放在第 00 格。游戏由二人轮流操作,这里我们不妨假设 Alice 先手。

轮到其中一位玩家进行操作时,这位玩家可以根据当前格子的 pp 值决定前进的步数。具体地说,假设当前棋子位于第 kk 格,那么当前进行操作的玩家可以将棋子向前移动 xx 格,其中 xx 可以是满足 1xpk1\le x\le p_k 的任意整数。如果玩家没有走满 pkp_k 格,即 x<pkx<p_k,那么该玩家可以在完成移动后选择是否进行一次挑战。如果选择不进行挑战,那么由另一位玩家进行下一轮操作。否则,如果当前玩家选择挑战,那么系统将会产生两个随机整数 uuvv,其中:uu 表示挑战的能量,它在 [1,pkx]\left[1, p_k-x\right] 中等概率产生;vv 表示挑战所需的活化能,它在 [0,qk+qk+x]\left[0, q_k + q_{k+x}\right] 中等概率产生。根据 uuvv 的值,系统会根据以下规则自动判定挑战结果:

如果 u>vu>v,则挑战成功,对方玩家的操作被跳过一轮,由当前玩家继续操作; 如果 u=vu=v,则挑战结果为平手,什么事情都不会发生,由对方玩家进行操作; 如果 u<vu<v,则挑战失败,当前玩家下一轮操作将会被跳过,即对方玩家可以连续操作两轮。 为了防止其中一方玩家一直被跳过,规定:

如果当前玩家通过自身的挑战获得额外操作机会,则该玩家在该额外操作机会中不能进行第二次挑战; 如果当前玩家通过对方玩家的挑战获得额外操作机会,则该玩家不能在其第一次操作结束时发起挑战,只能在第二次操作结束时选择是否进行挑战,并且当且仅当挑战成功时可以进行第三次操作。 需要注意的是,无论连续进行多少次操作,每次操作都需要将棋子向前移动至少 11 格。同大多数游戏一样,谁将棋子移动到终点(即编号为 nn 的格)谁就获胜。

Alice 和 Bob 都足够聪明,可以心算出对于当前棋子的位置,能使自己获胜概率最大的操作。作为一名旁观者,你没有他们那么强的心算能力;但是你也想通过自己编程的能力,计算出当 Alice 先手从第 00 格开始进行操作时,Alice 的胜率。

输入格式

输入的第一行包含一个正整数 nn,表示棋盘包含 (n+1)(n+1) 格,分别标号 0,1,,n0, 1, \cdots, n

输入的第二行包含 nn 个正整数 p0,p1,,pn1p_0, p_1, \cdots, p_{n-1},分别表示第 00 格至第 (n1)(n-1) 格的 pp 值。

输入的第三行包含 nn 个正整数 q0,q1,,qn1q_0, q_1, \cdots, q_{n-1},分别表示第 00 格至第 (n1)(n-1) 格的 qq 值。

输出格式

输出一个实数,表示 Alice 先手开始游戏的胜率。当你的输出与标准输出的绝对误差不超过 10610^{-6} 时,我们认为你的输出是正确的。

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 先手,由于可以直接从第 00 格移动到终点的第 33 格,Alice 会直接将棋子移动到第 33 格,故 Alice 必胜。

【样例解释 2】

Alice 先手,但是不能直接移动到第 33 格,并且无论结束操作时棋子在第 11 格还是第 22 格,Bob 都可以直接将其移动到终点的第 33 格,因此 Alice 必须尝试挑战。将棋子移动到第 11 格并发动挑战,挑战成功的概率为 1/41/4,故 Alice 的胜率为 1/41/4

【数据范围】

对于 100%100\% 的数据,保证 1n1000001\le n\le 1000001pi,qi3331\le p_i, q_i\le 333