← 返回题目列表

AtCoder · abc448_g

G. 征服

中文机器翻译题面 查看原题

分数: 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