P13246 [GCJ 2014 Qualification] Deceitful War

这是本轮比赛中最难理解的一道题。如果你是 Code Jam 的新手，建议先尝试解决其他题目。

Naomi 和 Ken 有时会一起玩游戏。在每局游戏开始前，他们每人会获得 $N$ 块看起来完全一样的木块，质量在 $0.0\,\text{kg}$ 到 $1.0\,\text{kg}$ 之间（不包括端点）。所有木块的质量彼此不同。他们可以用这些木块玩许多种游戏，但他们通常玩的游戏叫作 **War**（战争）。War 的规则如下： 1. 每位玩家会称量自己所有木块的质量，因此他们都知道自己所有木块的重量，但不知道对方木块的重量。 2. 他们会重复进行以下过程共 $N$ 次： 1. Naomi 选择她的一块木块，质量为 $\text{chosen}_{\text{Naomi}}$。 2. Naomi 将这块木块的质量告诉 Ken。 3. Ken 选择他的一块木块，质量为 $\text{chosen}_{\text{Ken}}$。 4. 他们分别将自己的木块放在天平的两边，质量较大的那一方获得一分。 5. 两块木块随后一同被焚毁。 Naomi 意识到了关于 War 的三件事。首先，她意识到自己经常输。其次，她意识到 Ken 有一个**唯一的**策略，可以在不假设 Naomi 策略的前提下最大化自己的得分，而 Ken 总是采用该策略。第三，她意识到自己讨厌输。因此 Naomi 决定不再玩 War，而是玩她自创的游戏，称为 **Deceitful War（欺诈战争）**。这个游戏的妙处在于，Ken 仍然以为他们在玩 War！ Deceitful War 的规则如下，区别于 War 的部分用**粗体**标出： 1. 每位玩家称量自己所有木块的质量。**Naomi 还会在 Ken 不注意时称量他的木块，因此 Naomi 知道所有木块的质量，而 Ken 只知道自己木块的质量。** 2. 他们会重复以下过程共 $N$ 次： 1. Naomi 选择她的一块木块，质量为 $\text{chosen}_{\text{Naomi}}$。 2. **Naomi 向 Ken 报出一个数 $\text{Told}_{\text{Naomi}}$，其值在 $0.0\,\text{kg}$ 到 $1.0\,\text{kg}$ 之间（不包括端点）。Ken 认为他们在玩 War，因此他会以为 Naomi 报的这个数就是她选择的木块的质量，即 $\text{chosen}_{\text{Naomi}}$。** 3. Ken 选择他的一块木块，质量为 $\text{chosen}_{\text{Ken}}$。 4. 他们将各自的木块放在天平两侧，质量较大的一方获得一分。 5. 两块木块随后一同被焚毁。 Naomi 不希望 Ken 发现她实际上并没有在玩 War。因此，在选择要使用的木块及要告知 Ken 的质量时，她必须确保天平不会揭示出 $\text{Chosen}_{\text{Naomi}} \neq \text{Told}_{\text{Naomi}}$。换句话说，她的决策必须满足以下条件： - 当且仅当 $\text{Chosen}_{\text{Naomi}} > \text{Chosen}_{\text{Ken}}$ 时，才有 $\text{Told}_{\text{Naomi}} > \text{Chosen}_{\text{Ken}}$； - $\text{Told}_{\text{Naomi}}$ 不得与 Ken 的任意一块木块的质量相等，因为他知道那是不可能的。 你可能会觉得 Naomi 通过欺骗并不能获得更多分数，因为 Ken 可能会发现她不是在玩 War；但 Naomi 知道 Ken 相信双方都在玩 War，而她也知道 Ken 会始终采用他在 War 中的最优策略，因此 Naomi 能预测 Ken 的每一步行动。 你将获得 Naomi 和 Ken 最初的木块质量数据。Naomi 将使用 Deceitful War 的最优策略来获得尽可能多的分数；Ken 将使用 War 的最优策略（假设双方都在玩 War）来获得尽可能多的分数。你的任务是计算： - 如果 Naomi 玩的是 Deceitful War，她最多能获得多少分？ - 如果 Naomi 玩的是 War，采用最优策略，她最多能获得多少分？ **示例说明** 如果每位玩家只剩下一块木块，Naomi 的质量是 $0.5\,\text{kg}$，Ken 的质量是 $0.6\,\text{kg}$，那么 Ken 保证得分。Naomi 无法声称她的木块质量是 $\geq 0.6\,\text{kg}$，否则当天平显示 Ken 的木块更重时，Ken 会发现她没有在玩 War。 如果每位玩家还剩两块木块，Naomi 拥有 $[0.7\,\text{kg}, 0.2\,\text{kg}]$，Ken 拥有 $[0.8\,\text{kg}, 0.3\,\text{kg}]$，那么 Naomi 可以选择她的 $0.2\,\text{kg}$ 木块，并对 Ken 谎称其质量是 $0.6\,\text{kg}$。Ken 会误以为 Naomi 说的是真话（因为他以为他们在玩 War），于是他会选择他的 $0.8\,\text{kg}$ 木块来争取得分。Ken 的确得了一分，却没有意识到自己被骗了，因为天平确实显示他的木块更重。接下来 Naomi 可以使用她的 $0.7\,\text{kg}$ 木块，并如实告诉 Ken，它的质量是 $0.7\,\text{kg}$，从而赢得该轮得分。 若 Naomi 此前没有欺骗，而是一直玩 War，那么 Ken 会赢得两分，Naomi 将一分未得。

输入的第一行是测试用例数量 $T$。接下来的 $T$ 组测试数据中，每组测试数据的第一行是一个整数 $N$，表示每位玩家拥有的木块数量。第二行是 $N$ 个用空格分隔的实数，表示 Naomi 拥有的木块质量（单位为 kg）。第三行是 $N$ 个用空格分隔的实数，表示 Ken 拥有的木块质量（单位为 kg）。 所有 Naomi 和 Ken 的木块质量都以 $0$ 开头的小数形式给出，且具有 $1$ 到 $5$ 位小数。尽管输入中的质量数值都保留了 $1$ 到 $5$ 位小数，Naomi 和 Ken 并不知道这一点；因此 Naomi 仍然可以向 Ken 报一个例如 $0.5000001\,\text{kg}$ 的质量值，而 Ken 不会怀疑她。

对于每组测试数据，输出一行 `"Case #x: y z"`，其中 $x$ 是当前测试用例的编号（从 $1$ 开始），$y$ 是 Naomi 采用 Deceitful War 最优策略时的得分，$z$ 是她采用 War 最优策略时的得分。

**限制条件** - $1 \leq T \leq 50$； - 所有 Naomi 和 Ken 的木块质量彼此不同，且位于 $0.0$ 与 $1.0$ 之间（不包括端点）。 **小数据集** - 时间限制：~~60~~ 3 秒； - $1 \leq N \leq 10$。 **大数据集** - 时间限制：~~120~~ 5 秒； - $1 \leq N \leq 1000$。 翻译由 ChatGPT-4o 完成。