A2554. 三国围棋擂台赛
编程题
提高+/省选-
知识点
题目描述
一年一度的“农心杯”三国围棋擂台赛是世界上最高水平的围棋比赛，也是中日韩三国围棋界最激动人心的较量。本题就是建立在这一比赛的规则之上。
三国围棋擂台赛是三个国家的代表队之间的比赛，下面简要介绍一下比赛的规则：
1.不妨设三个国家分别为$A$、$B$和$C$，每个国家各有$n$名选手（在上述的实际比赛中$n = 5$），分别称其为$A_1$，$A_2$，…，$A_n$，$B_1$，$B_2$，…，$B_n$，$C_1$，$C_2$，…，$C_n$。
2.每场比赛都能分出胜负。每场比赛的负者遭到淘汰。
3.每队第一位出场的选手都已经确定为每队的第$n$位选手，即$A_n$、$B_n$和 $C_n$。
4.通过抽签等概率地选出一支队伍。该队将在第一轮中轮空，而剩下的两支队伍的第$n$位选手将进行第一场比赛。
5.第一场比赛的胜者（这里的胜者是指赢得该局比赛的选手，下同）与轮空队伍的第$n$位选手进行第二场比赛。比如在第一场比赛中$C_n$战胜了$A_n$，则第二场则由$C_n$对阵$B_n$。
6.从第三场比赛开始，前一场比赛未参加的队伍将选出一个未被淘汰的选手与上一场比赛的胜者进行下一场比赛。
7.这个过程将一直进行，直到某个队伍的全部参赛选手都被淘汰为止。
8.当只有两支队伍的时候，每场比赛后，由负方选择一位未被淘汰的选手与胜者进行下一场比赛。
9.当两支队伍中的任意一队的全部选手均被淘汰后比赛结束，余下的那支队伍将获得农心杯。
新一届的比赛就要开始了。你作为$A$队的领队，在比赛开始前已经统计了这$3n$位选手之间的胜率——即对于来自不同队伍的两个选手$Q$和$R$，我们已知$Q$战胜$R$的概率为$p$（$0 \leq p \leq 1$），且$R$战胜$Q$的概率为$1-p$。
由于你所在的国家实力超群，可以认为剩下的两只队伍都将矛头对准了你。$B$、$C$队的每个决策，即派出选手的顺序的目的都是使你所在的国家（$A$队）夺冠的概率尽可能小，而$A$队的决策的目的必然是使最后夺冠的概率尽可能大。你要做的事情就是计算出在这种极为不利的情况下，在三方都做出最优决策的前提下，$A$队夺冠的期望$E_A$。
关于期望的计算：设现在在场上比赛的人是$Q$和$R$，$Q$胜$R$的概率为$p$，则此时$A$队胜率的期望
$E_A = p$ × $E_1 + (1 - p)$ × $E_2$
其中$E_1$为$Q$胜$R$后$A$队夺冠的期望，$E_2$为$R$胜$Q$后$A$队夺冠的期望。$E_1$、$E_2$则同样使用上式递归计算。
$A$队的决策会尽可能使这个期望尽可能大，而$B$、$C$队则会使这个期望尽可能小。当$B$、$C$队的全部选手都被淘汰后夺冠期望为$1$，$A$队所有队员被淘汰后期望为$0$。
例如当每队有$3$位参赛选手时，相互之间的胜率由如下的$3$个$3*3$的矩阵给出，其中矩阵中的每个数值$p$为所在行选手对于所在列选手的胜率，所在列选手对于所在行选手的胜率为$1-p$。
三支队的第三位选手的水平相同，在第两局比赛后，三支队的选手获胜的概率是相同的。假设第二局获胜的是$B_3$，第三局轮到$A$队出场。这时我们可以派出$A_1$和$A_2$两种选择。
如果派出$A_2$，虽然第三局一定可以战胜$B_3$（胜率为$100 \%$），但是$C$队会在第四场比赛中派出$C_2$，$A_2$对于$C_2$必败（胜率为$0$），第五场中$B$队会让$B_1$出场，第六场$A_1$只能出场，这时对$A_1$必胜的$B_2$还未登场，因此$A_1$迟早会遭到淘汰，$A$队夺冠的概率就为$0$。
如果派出$A_1$，虽然本局对于$B_3$比赛只有$50 \%$的胜率，但是夺冠的概率为$6.25 \%$；因此在第三场应该派出$A_1$。
根据第三场比赛的参赛选手的六种情况，最后夺冠的期望为：
$$ \dfrac{(6.25\%+3.125\%+18.75\%+25\%+60.9375\%+50\%)}{6} = 27.34375\%$$
三国围棋擂台赛是三个国家的代表队之间的比赛，下面简要介绍一下比赛的规则：
1.不妨设三个国家分别为$A$、$B$和$C$，每个国家各有$n$名选手（在上述的实际比赛中$n = 5$），分别称其为$A_1$，$A_2$，…，$A_n$，$B_1$，$B_2$，…，$B_n$，$C_1$，$C_2$，…，$C_n$。
2.每场比赛都能分出胜负。每场比赛的负者遭到淘汰。
3.每队第一位出场的选手都已经确定为每队的第$n$位选手，即$A_n$、$B_n$和 $C_n$。
4.通过抽签等概率地选出一支队伍。该队将在第一轮中轮空，而剩下的两支队伍的第$n$位选手将进行第一场比赛。
5.第一场比赛的胜者（这里的胜者是指赢得该局比赛的选手，下同）与轮空队伍的第$n$位选手进行第二场比赛。比如在第一场比赛中$C_n$战胜了$A_n$，则第二场则由$C_n$对阵$B_n$。
6.从第三场比赛开始，前一场比赛未参加的队伍将选出一个未被淘汰的选手与上一场比赛的胜者进行下一场比赛。
7.这个过程将一直进行，直到某个队伍的全部参赛选手都被淘汰为止。
8.当只有两支队伍的时候，每场比赛后，由负方选择一位未被淘汰的选手与胜者进行下一场比赛。
9.当两支队伍中的任意一队的全部选手均被淘汰后比赛结束，余下的那支队伍将获得农心杯。
新一届的比赛就要开始了。你作为$A$队的领队，在比赛开始前已经统计了这$3n$位选手之间的胜率——即对于来自不同队伍的两个选手$Q$和$R$，我们已知$Q$战胜$R$的概率为$p$（$0 \leq p \leq 1$），且$R$战胜$Q$的概率为$1-p$。
由于你所在的国家实力超群，可以认为剩下的两只队伍都将矛头对准了你。$B$、$C$队的每个决策，即派出选手的顺序的目的都是使你所在的国家（$A$队）夺冠的概率尽可能小，而$A$队的决策的目的必然是使最后夺冠的概率尽可能大。你要做的事情就是计算出在这种极为不利的情况下，在三方都做出最优决策的前提下，$A$队夺冠的期望$E_A$。
关于期望的计算：设现在在场上比赛的人是$Q$和$R$，$Q$胜$R$的概率为$p$，则此时$A$队胜率的期望
$E_A = p$ × $E_1 + (1 - p)$ × $E_2$
其中$E_1$为$Q$胜$R$后$A$队夺冠的期望，$E_2$为$R$胜$Q$后$A$队夺冠的期望。$E_1$、$E_2$则同样使用上式递归计算。
$A$队的决策会尽可能使这个期望尽可能大，而$B$、$C$队则会使这个期望尽可能小。当$B$、$C$队的全部选手都被淘汰后夺冠期望为$1$，$A$队所有队员被淘汰后期望为$0$。
例如当每队有$3$位参赛选手时，相互之间的胜率由如下的$3$个$3*3$的矩阵给出，其中矩阵中的每个数值$p$为所在行选手对于所在列选手的胜率，所在列选手对于所在行选手的胜率为$1-p$。
三支队的第三位选手的水平相同，在第两局比赛后，三支队的选手获胜的概率是相同的。假设第二局获胜的是$B_3$，第三局轮到$A$队出场。这时我们可以派出$A_1$和$A_2$两种选择。
如果派出$A_2$，虽然第三局一定可以战胜$B_3$（胜率为$100 \%$），但是$C$队会在第四场比赛中派出$C_2$，$A_2$对于$C_2$必败（胜率为$0$），第五场中$B$队会让$B_1$出场，第六场$A_1$只能出场，这时对$A_1$必胜的$B_2$还未登场，因此$A_1$迟早会遭到淘汰，$A$队夺冠的概率就为$0$。
如果派出$A_1$，虽然本局对于$B_3$比赛只有$50 \%$的胜率，但是夺冠的概率为$6.25 \%$；因此在第三场应该派出$A_1$。
根据第三场比赛的参赛选手的六种情况，最后夺冠的期望为：
$$ \dfrac{(6.25\%+3.125\%+18.75\%+25\%+60.9375\%+50\%)}{6} = 27.34375\%$$
输入格式
输入文件为go.in。
第一行包括一个整数$n$，表示每队的选手数。
第二行到第$n + 1$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$A$队对$B$队的胜率。其中第$i + 1$行的第$j$个数表示选手$A_i$对选手$B_j$时的胜率。
第$n + 2$行为空行。
第$n + 3$行到第$2n + 2$行每行包含$n$个实数，同样为一个$n*n$的矩阵，表示$A$队对$C$队的胜率。其中第$i + n + 2$行的第$j$个数表示选手$A_i$对选手$C_j$时的胜率。
第$2n + 3$行为空行。
第$2n + 4$行到第$3n + 3$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$B$队对$C$队的胜率。其中第$i + 2n + 3$行的第$j$个数表示选手$B_i$对选手$C_j$时的胜率。
第一行包括一个整数$n$，表示每队的选手数。
第二行到第$n + 1$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$A$队对$B$队的胜率。其中第$i + 1$行的第$j$个数表示选手$A_i$对选手$B_j$时的胜率。
第$n + 2$行为空行。
第$n + 3$行到第$2n + 2$行每行包含$n$个实数，同样为一个$n*n$的矩阵，表示$A$队对$C$队的胜率。其中第$i + n + 2$行的第$j$个数表示选手$A_i$对选手$C_j$时的胜率。
第$2n + 3$行为空行。
第$2n + 4$行到第$3n + 3$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$B$队对$C$队的胜率。其中第$i + 2n + 3$行的第$j$个数表示选手$B_i$对选手$C_j$时的胜率。
输出格式
输出文件go.out仅包含一个实数，保留$6$位小数，表示$A$队获得冠军的概率。
输入输出样例
输入 #1
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
输出 #1
0.273438
说明/提示
$30\%$的数据中，$n \leq 4$。
$40\%$的数据中，$n \leq 5$。
$100\%$的数据中，$n \leq 7$。
对于$10\%$的数据有三个胜率矩阵中，每个矩阵的元素都相同，但不同矩阵的数字可能不同。
$40\%$的数据中，$n \leq 5$。
$100\%$的数据中，$n \leq 7$。
对于$10\%$的数据有三个胜率矩阵中，每个矩阵的元素都相同，但不同矩阵的数字可能不同。