#P4190. [CTSC2010] 三国围棋擂台赛

[CTSC2010] 三国围棋擂台赛

题目描述

一年一度的“农心杯”三国围棋擂台赛是世界上最高水平的围棋比赛,也是中日韩三国围棋界最激动人心的较量。本题就是建立在这一比赛的规则之上。

三国围棋擂台赛是三个国家的代表队之间的比赛,下面简要介绍一下比赛的规则:

  1. 不妨设三个国家分别为 AABBCC,每个国家各有nn名选手(在上述的实际比赛中n=5n = 5),分别称其为A1A_1A2A_2,…,AnA_nB1B_1B2B_2,…,BnB_nC1C_1C2C_2,…,CnC_n

  2. 每场比赛都能分出胜负。每场比赛的负者遭到淘汰。

  3. 每队第一位出场的选手都已经确定为每队的第nn位选手,即 AnA_nBnB_nCnC_n

  4. 通过抽签等概率地选出一支队伍。该队将在第一轮中轮空,而剩下的两支队伍的第 nn 位选手将进行第一场比赛。

  5. 第一场比赛的胜者(这里的胜者是指赢得该局比赛的选手,下同)与轮空队伍的第 nn 位选手进行第二场比赛。比如在第一场比赛中 CnC_n 战胜了 AnA_n,则第二场则由CnC_n对阵BnB_n

  6. 从第三场比赛开始,前一场比赛未参加的队伍将选出一个未被淘汰的选手与上一场比赛的胜者进行下一场比赛。

  7. 这个过程将一直进行,直到某个队伍的全部参赛选手都被淘汰为止。

  8. 当只有两支队伍的时候,每场比赛后,由负方选择一位未被淘汰的选手与胜者进行下一场比赛。

  9. 当两支队伍中的任意一队的全部选手均被淘汰后比赛结束,余下的那支队伍将获得农心杯。

新一届的比赛就要开始了。你作为 AA 队的领队,在比赛开始前已经统计了这 3n3n 位选手之间的胜率——即对于来自不同队伍的两个选手 QQRR,我们已知 QQ 战胜 RR 的概率为 pp0p10 \leq p \leq 1),且RR战胜 QQ 的概率为 1p1-p

由于你所在的国家实力超群,可以认为剩下的两只队伍都将矛头对准了你。BBCC 队的每个决策,即派出选手的顺序的目的都是使你所在的国家(AA 队)夺冠的概率尽可能小,而AA队的决策的目的必然是使最后夺冠的概率尽可能大。你要做的事情就是计算出在这种极为不利的情况下,在三方都做出最优决策的前提下,AA 队夺冠的期望 EAE_A

关于期望的计算:设现在在场上比赛的人是 QQRRQQRR的概率为 pp,则此时 AA 队胜率的期望

EA=pE_A = p × E1+(1p)E_1 + (1 - p) × E2E_2

其中 E1E_1QQRRAA 队夺冠的期望,E2E_2RRQQAA 队夺冠的期望。E1E_1E2E_2 则同样使用上式递归计算。

AA 队的决策会尽可能使这个期望尽可能大,而 BBCC 队则会使这个期望尽可能小。当 BBCC 队的全部选手都被淘汰后夺冠期望为 11AA 队所有队员被淘汰后期望为 00

例如当每队有 33 位参赛选手时,相互之间的胜率由如下的333×33\times 3 的矩阵给出,其中矩阵中的每个数值pp 为所在行选手对于所在列选手的胜率,所在列选手对于所在行选手的胜率为 1p1-p

三支队的第三位选手的水平相同,在第两局比赛后,三支队的选手获胜的概率是相同的。假设第二局获胜的是 B3B_3,第三局轮到 AA 队出场。这时我们可以派出 A1A_1A2A_2 两种选择。

如果派出 A2A_2,虽然第三局一定可以战胜 B3B_3(胜率为100%100 \%),但是 CC 队会在第四场比赛中派出 C2C_2A2A_2 对于 C2C_2 必败(胜率为 00),第五场中 BB 队会让 B1B_1 出场,第六场 A1A_1 只能出场,这时对 A1A_1 必胜的 B2B_2 还未登场,因此 A1A_1 迟早会遭到淘汰,AA 队夺冠的概率就为 00

如果派出A1A_1,虽然本局对于 B3B_3 比赛只有 50%50 \% 的胜率,但是夺冠的概率为 6.25%6.25 \%;因此在第三场应该派出 A1A_1

根据第三场比赛的参赛选手的六种情况,最后夺冠的期望为:

$$\dfrac{(6.25\%+3.125\%+18.75\%+25\%+60.9375\%+50\%)}{6} = 27.34375\% $$

输入格式

输入文件为 go.in。

第一行包括一个整数 nn,表示每队的选手数。

第二行到第 n+1n + 1 行每行包含 nn 个实数,整体为一个n×nn\times n 的矩阵,表示 AA 队对 BB 队的胜率。其中第i+1i + 1 行的第 jj 个数表示选手 AiA_i 对选手 BjB_j 时的胜率。

n+2n + 2 行为空行。

n+3n + 3 行到第 2n+22n + 2 行每行包含 nn 个实数,同样为一个 n×nn\times n 的矩阵,表示 AA 队对 CC 队的胜率。其中第 i+n+2i + n + 2 行的第 jj 个数表示选手 AiA_i 对选手 CjC_j 时的胜率。

2n+32n + 3 行为空行。

2n+42n + 4 行到第 3n+33n + 3 行每行包含 nn 个实数,整体为一个 n×nn\times n 的矩阵,表示 BB 队对 CC 队的胜率。其中第 i+2n+3i + 2n + 3 行的第 jj 个数表示选手 BiB_i 对选手 CjC_j 时的胜率。

输出格式

输出文件 go.out 仅包含一个实数,保留 66 位小数,表示AA队获得冠军的概率。

3
1.0 0.0 0.5
0.5 1.0 1.0
0.5 0.5 0.5

0.5 0.5 1.0
0.5 0.0 0.5
0.5 0.5 0.5

0.5 0.0 1.0
0.5 0.5 0.5
0.5 0.5 0.5 

0.273438

提示

30%30\% 的数据中,n4n \leq 4

40%40\% 的数据中,n5n \leq 5

100%100\% 的数据中,n7n \leq 7

对于 10%10\% 的数据有三个胜率矩阵中,每个矩阵的元素都相同,但不同矩阵的数字可能不同。