分数: 675 点
问题陈述
高桥和青木玩纸牌游戏。游戏按照以下规则进行。
- 高桥展示套牌 A_1, A_2, \dots, A_N。这里 N \geq 3.
- 青木展示套牌 B_1, B_2, B_3.
- 高桥从青木的牌组中选择一张牌并将其禁止。青木也从高桥的套牌中选择一张套牌并将其禁止。执行这两个禁止操作 同时。 (也就是说,两个玩家都不能根据对方的选择采取行动。)
- 然后,高桥和青木各 同时 声明他们将使用自己展示的牌组中的哪副牌。然而,禁止的牌组不能被宣告。
- 然后,两名玩家使用他们声明的牌组战斗一次。结果,其中一人获胜。
给你整数 X_{i,j} (1 \leq i \leq N, 1 \leq j \leq 3)。让 p_{i,j} = \dfrac{X_{i,j}}{10^6}. p_{i,j} 是高桥使用套牌时的胜率 A_i 和青木使用甲板 B_j。高桥和青木都知道的价值观
提前 p_{i,j} 。
求当两名玩家都最大化自己的胜率时,高桥的胜率。
T 给出了测试用例;解决它们中的每一个。
当两名玩家都最大化自己的胜率时,高桥的胜率是多少?
在每个阶段,每个玩家分配的概率总和为 1 根据迄今为止所揭示的信息来确定可用的选择,并根据这些概率随机选择一个选择。每个玩家选择一种最大化“最小可能胜率”的策略,即“当对手选择使玩家胜率最小化的策略时的胜率”。如果有多个策略满足该条件,则可以选择其中任何一个。
当两个玩家都按照这个策略行动时,无论选择什么具体策略,高桥的胜率都是唯一确定的。求这个值。
约束
- 1 \leq T \leq 500
- 3 \leq N \leq 5 \times 10^4
- 0 \leq X_{i,j} \leq 10^6
- 总和 N 所有测试用例最多 5 \times 10^4.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i- 第一个测试用例。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
对于每个测试用例,输入按以下格式给出。
N
X_{1,1} X_{1,2} X_{1,3}
X_{2,1} X_{2,2} X_{2,3}
\vdots
X_{N,1} X_{N,2} X_{N,3}
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,输出当两个玩家都采取行动以最大化自己的胜率时高桥的胜率。如果与真实值的绝对或相对误差最多为,则输出被认为是正确的 10^{-6}.
示例输入 1
1 3 600000 500000 100000 400000 700000 300000 800000 200000 900000
示例输出 1
0.5272727272727272
当双方都最大化自己的胜率时,高桥的胜率是 0.5272727 \cdots.
示例输入 2
3 6 402522 269943 705465 529104 292257 262398 598965 708517 393767 10680 760196 459175 163269 555933 100458 252724 762224 143581 4 720086 398924 165990 446155 678065 592893 674921 176800 484411 222632 81476 633357 5 212176 543920 484352 23874 760886 95861 291354 504948 790821 523486 327166 289413 621589 178581 628701
示例输出 2
0.5136657634439492 0.5120053615937050 0.5396248345565982
示例输入 3
6 3 600000 300000 100000 0 400000 600000 700000 400000 100000 3 700000 700000 200000 0 0 900000 500000 600000 900000 5 1000000 658525 1000000 867635 1000000 259903 727305 342912 1000000 995128 432824 1000000 69492 105991 1000000 6 900000 700000 300000 600000 300000 500000 900000 100000 900000 900000 1000000 0 800000 200000 900000 700000 800000 900000 7 300000 900000 800000 600000 1000000 700000 700000 200000 1000000 1000000 200000 200000 200000 400000 1000000 500000 800000 900000 900000 500000 800000 5 500000 500000 41274 270488 520436 605863 247128 522516 149943 502751 491747 516407 503752 488744 31814
示例输出 3
0.3520000000000000 0.5571428571428572 0.9951279999999999 0.8478260869565216 0.8336956521739129 0.4988562153245037