P16652 [GKS 2018 #E] Board Game

Bahu 正在和 Bala 玩一款棋盘游戏。每位玩家拥有 $3 \cdot N$ 张军队卡牌，每张卡牌具有不同的力量值。游戏中有 $3$ 个战场。每位玩家必须将他们的卡牌面朝下分配到各个战场中，使得每个战场恰好获得 $N$ 张自己的卡牌。 当游戏开始时，所有卡牌将被翻开。对于每个战场，每位玩家将该战场中自己 $N$ 张卡牌的力量值相加，然后双方比较这些总和。如果一方总和更高，则该方赢得该战场。如果总和相同，则 Bala 赢得该战场；这是他的特殊优势。 游戏的最终赢家是赢得最多战场的玩家（由于有 $3$ 个战场，保证不会出现总平局）。 Bala 认为他的优势足以让他获胜，因此他只是随机洗牌，并将前 $N$ 张放到第一个战场，接下来 $N$ 张放到第二个战场，最后 $N$ 张放到第三个战场。 尽管 Bahu 处于劣势，他仍然试图获胜！求如果 Bahu 以最优方式分配他的卡牌，他获胜的概率。注意，Bala 的所有卡牌都是面朝下的，因此 Bahu 必须在看到 Bala 的卡牌分布之前选择自己的卡牌分布。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例；每个测试用例由三行组成。第一行包含一个整数 $N$，如上所述。第二行包含 $3 \cdot N$ 个整数 $A_0, A_1, \dots, A_{3N-1}$，表示 Bahu 卡牌的力量值。第三行包含 $3 \cdot N$ 个整数 $B_0, B_1, \dots, B_{3N-1}$，表示 Bala 卡牌的力量值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述概率。如果答案与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

在样例 #1 中，Bahu 可以将卡牌 $(2,2,2)$ 放在第一个战场，$(2,2,3)$ 放在第二个战场，$(2,2,3)$ 放在第三个战场。由于 Bala 的所有卡牌都是 $2$，Bala 赢得第一个战场，Bahu 赢得第二和第三个战场。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le A_i \le 10^6$。 对于所有 $i$，$1 \le B_i \le 10^6$。 **小数据集（测试集 1 – 可见）** $N = 3$。 **大数据集（测试集 2 – 隐藏）** $3 \le N \le 5$。 翻译由 DeepSeek V4 Pro 完成