P13066 [GCJ 2020 #3] Naming Compromise

Cameron 和 Jamie 即将迎来他们的第二个孩子。他们在育儿方面已经配合得很好了，但此刻却在一个关键问题上产生了分歧！Cameron 想给孩子取名为 $\mathbf{C}$，而 Jamie 则想取名为 $\mathbf{J}$。 你希望帮助他们找到一个折中的名字，使其尽可能接近双方的想法。你认为可以通过**编辑距离**的概念来实现这一点。两个字符串 $S_1$ 和 $S_2$ 之间的编辑距离是指将 $S_1$ 转换为 $S_2$ 所需的最少操作次数，允许的操作包括： * 在字符串任意位置插入一个字符。 * 删除字符串中的任意一个字符。 * 将字符串中的一个字符替换为其他任意字符。 例如，CAMERON 和 JAMIE 之间的编辑距离为 5。一种用 5 步完成转换的方式如下：CAMERON → JAMERON（替换）→ JAMIERON（插入）→ JAMIEON（删除）→ JAMIEN（删除）→ JAMIE（删除）。从 CAMERON 转换到 JAMIE 至少需要这么多操作。 为了使折中名字 $N$ 尽可能接近父母的原始意愿，你需要选择一个非空字符串 $N$，使得 $\mathbf{C}$ 与 $N$ 的编辑距离和 $\mathbf{J}$ 与 $N$ 的编辑距离之和最小。在所有满足这一条件的 $N$ 中，为了确保公平性，你还必须选择一个使得这两个编辑距离之差也尽可能小的 $N$。请为 Cameron 和 Jamie 找到一个折中名字。

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含一行，其中有两个字符串 $\mathbf{C}$ 和 $\mathbf{J}$，分别表示 Cameron 和 Jamie 提议的婴儿名字。这些名字均由大写英文字母组成。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足题目要求的名字。注意，$y$ 必须仅包含大写英文字母。

**样例解释** 样例测试集 1 符合测试集 1 的限制。另一个不符合这些限制但可能出现在测试集 2 中的样例见下文。 在样例 #1 中，从 `XYZZY` 到 `ZZY` 的编辑距离为 2（删除前两个字母），从 `ZZYZX` 到 `ZZY` 的编辑距离为 2（删除最后两个字母）。`XZZX` 和 `ZYYZY` 也是可行的解。没有其他名字能使编辑距离之和小于 4。 例如，`ZY` 到 `C` 和 `J` 的编辑距离相同（均为 3），但编辑距离之和为 6，并非最小值，因此不是可接受的答案。 `XZZY` 也不符合要求。它到 `C` 和 `J` 的编辑距离分别为 1 和 3。虽然编辑距离之和是最小的，但两者之差（$|1-3| = 2$）并非最小，因为我们已经证明可以找到差值为 0 的解。 在样例 #2 中，`Y` 和 `Z` 是唯一可接受的答案。 在样例 #3 中，注意输入的长度限制不适用于输出，因此所示答案在任一测试集中均可接受。另一个可能的答案是 `YYXXY`。 在样例 #4 中，`XZXZXZ` 到 `ZYZX` 的编辑距离为 3，`YZ` 到 `ZYZX` 的编辑距离为 2。编辑距离之和为 5，差值为 1；这些值是该情况下的最优解。 **数据范围** - $1 \leq T \leq 100$。 - $\mathbf{C} \neq \mathbf{J}$。 **测试集 1（4 分，可见判定）** - $1 \leq \text{C 的长度} \leq 6$。 - $1 \leq \text{J 的长度} \leq 6$。 - $\mathbf{C}$ 的第 $i$ 个字母是大写 X、Y 或 Z。 - $\mathbf{J}$ 的第 $i$ 个字母是大写 X、Y 或 Z。 **测试集 2（8 分，隐藏判定）** - $1 \leq \text{C 的长度} \leq 60$。 - $1 \leq \text{J 的长度} \leq 60$。 - $\mathbf{C}$ 的第 $i$ 个字母是大写英文字母。 - $\mathbf{J}$ 的第 $i$ 个字母是大写英文字母。 翻译由 DeepSeek V3 完成