#P13066. [GCJ 2020 #3] Naming Compromise

    ID: 12871 Type: RemoteJudge 20000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>动态规划 DP2020Special JudgeGoogle Code Jam

[GCJ 2020 #3] Naming Compromise

题目描述

Cameron and Jamie are about to welcome a second baby into their lives. They are already good at working together as parents, but right now they are disagreeing about one crucial thing! Cameron wants to name the baby one name (the string C\mathbf{C}), whereas Jamie wants to name the baby something else (the string J\mathbf{J}).

You want to help them find a compromise name that is as close as possible to what each of them wants. You think you can do this using the notion of edit distance. The edit distance between two strings S1S_1 and S2S_2 is the minimum number of operations required to transform S1S_1 into S2S_2, where the allowed operations are as follows:

  • Insert one character anywhere in the string.
  • Delete one character from anywhere in the string.
  • Change one character in the string to any other character.

For example, the edit distance between CAMERON and JAMIE is 5. One way to accomplish the transformation in 5 steps is the following: CAMERON to JAMERON (change) to JAMIERON (insert) to JAMIEON (delete) to JAMIEN (delete) to JAMIE (delete). Any transformation from CAMERON into JAMIE requires at least this many operations.

To make the compromise name NN as close as possible to the original desires of the parents, you want NN to be a non-empty string such that the sum of the edit distances between C\mathbf{C} and NN and between J\mathbf{J} and NN is as small as possible. Out of all those choices for NN, to make sure the compromise is fair, you must choose an NN such that the difference between those two edit distances is also as small as possible. Please find a compromise name for Cameron and Jamie.

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow. Each case consists of a single line with two strings C\mathbf{C} and J\mathbf{J}: the names that Cameron and Jamie have proposed for the baby, respectively. Each of these names is made up of uppercase English alphabet letters.

输出格式

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is a name that meets the requirements mentioned in the statement. Note that yy must contain only uppercase English letters.

4
XYZZY ZZYZX
Y Z
YYXXYZ ZYYXXY
XZXZXZ YZ
Case #1: ZZY
Case #2: Z
Case #3: ZYYXXYZ
Case #4: ZYZX
1
GCJ ABC
Case #1: GC

提示

Sample Explanation

Sample Test Set 1 meets the limits for Test Set 1. Another sample case that does not meet those limits but could appear in Test Set 2.

The above cases meet the limits for Test Set 1. Another sample case that does not meet those limits appears at the end of this section.

In Sample Case #1, the edit distance from XYZZY to ZZY is 2 (delete the first two letters), and the edit distance from ZZYZX to ZZY is 2 (delete the last two letters). XZZX and ZYYZY would also work. No possible name has a sum of edit distances that is less than 4.

ZY, for example, has the same edit distance to C as to J (3, in each case). However the sum of those distances would be 6, which is not minimal, so it would not be an acceptable answer.

XZZY is also unacceptable. Its edit distances to C and J, respectively, are 1 and 3. The sum of those edit distances is minimal, but the difference between the two (13=2|1-3| = 2) is not minimal, since we have shown that it is possible to achieve a difference of 0.

In Sample Case #2, Y and Z are the only acceptable answers.

In Sample Case #3, notice that input length restrictions do not apply to the output, so the shown answer is acceptable in either test set. Another possible answer is YYXXY.

In Sample Case #4, the edit distance between XZXZXZ and ZYZX is 3, and the edit distance between YZ and ZYZX is 2. The sum of those edit distances is 5, and their difference is 1; these values are optimal for this case.

Limits

  • 1T1001 \leq T \leq 100.
  • CJ\mathbf{C} \neq \mathbf{J}.

Test Set 1 (4 Pts, Visible Verdict)

  • 1length of C61 \leq \text{length of } \mathbf{C} \leq 6.
  • 1length of J61 \leq \text{length of } \mathbf{J} \leq 6.
  • The i-th letter of C\mathbf{C} is an uppercase x, y, or z, for all i.
  • The i-th letter of J\mathbf{J} is an uppercase x, y, or z, for all i.

Test Set 2 (8 Pts, Hidden Verdict)

  • 1length of C601 \leq \text{length of } \mathbf{C} \leq 60.
  • 1length of J601 \leq \text{length of } \mathbf{J} \leq 60.
  • The ii-th letter of C\mathbf{C} is an uppercase English alphabet letter, for all i.
  • The ii-th letter of J\mathbf{J} is an uppercase English alphabet letter, for all i.