P13205 [GCJ 2016 #3] Go++

Go 语言的设计目标是提供简单的 API 并支持多线程。Code Jam 团队希望将这些目标发挥到极致，因此我们提出了一种新语言，名为 Go++。 Go++ 语言只使用一个寄存器，该寄存器存储一个布尔值（0 或 1）。寄存器初始值为 0。该语言有三种指令： * $\mathbf{0}$，将寄存器设置为 0。 * $\mathbf{1}$，将寄存器设置为 1。 * $\mathbf{?}$，输出当前寄存器的值。 很简单，对吧？为了支持多线程，我们允许两段不同的 Go++ 程序同时运行，并共享同一个寄存器。每条指令都是原子的——也就是说，每条指令必须完全执行完毕后，下一条指令才能开始执行。不过，两段程序的指令可以以任意方式交错执行，只要每段程序内部指令的相对顺序不变。 例如，下面是将两段程序 $1\mathbf{?}$ 和 $\mathbf{?} \mathbf{0}$ 同时执行时所有可能的六种交错方式（下划线仅用于区分第二段程序的指令）： * $\mathbf{?}\mathbf{0}1\mathbf{?}$，输出为 $\mathbf{0\ 1}$。（记住寄存器初始为 0。） * $\mathbf{?}1\mathbf{0}\mathbf{?}$，输出为 $\mathbf{0\ 0}$。 * $\mathbf{?}1\mathbf{?}\mathbf{0}$，输出为 $\mathbf{0\ 1}$。 * $1\mathbf{?}\mathbf{0}\mathbf{?}$，输出为 $\mathbf{1\ 0}$。 * $1\mathbf{?}\mathbf{?}\mathbf{0}$，输出为 $\mathbf{1\ 1}$。 * $1\mathbf{?}\mathbf{?}\mathbf{0}$，输出为 $\mathbf{1\ 1}$。 注意，输出字符串始终只包含 $\mathbf{0}$ 和 $\mathbf{1}$，而不会有 $\mathbf{?}$，因为 $\mathbf{?}$ 不是寄存器的状态。 通常，程序员会写程序以产生期望的输出，而你的任务则是编写两段程序，保证不会产生某个“不良输出”！具体来说，你会得到一个长度为 $\mathbf{L}$ 的“不良字符串” $\mathbf{B}$，以及一个包含 $\mathbf{N}$ 个长度为 $\mathbf{L}$ 的“良好字符串”集合 $\mathbf{G}$。你需要构造两段 Go++ 程序（长度可以不同），使得两段程序以上述规则交错执行时，能够产生 $\mathbf{G}$ 中所有字符串，但绝不可能产生字符串 $\mathbf{B}$。如果还能产生其他既不是 $\mathbf{B}$ 也不在 $\mathbf{G}$ 的字符串，也没关系。注意，两段程序中 $\mathbf{?}$ 指令的总数必须恰好为 $\mathbf{L}$。两段程序总指令数不得超过 200。 举例来说，若 $\mathbf{B}=\mathbf{11}$，$\mathbf{G}=\{\mathbf{10}, \mathbf{00}\}$，则程序 $\mathbf{?}$ 和 $\mathbf{10?1}$ 是一个合法答案。它们能产生 $\mathbf{G}$ 中的所有字符串，但无论如何交错都不可能产生 $\mathbf{B}$。（它们也能产生 $\mathbf{01}$，但这既不是 $\mathbf{B}$ 也不在 $\mathbf{G}$，这没关系。）而程序 $1\mathbf{?}$ 和 $\mathbf{?}\mathbf{0}$ 不是合法答案，因为它们可能产生 $\mathbf{B}$。程序 $\mathbf{00}$ 和 $\mathbf{??}$ 也不是合法答案，因为它们无法产生 $\mathbf{G}$ 中的所有字符串。 你能否构造出满足条件的两段程序，或判断任务不可能完成（IMPOSSIBLE）？

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组三行。每组的第一行为两个整数 $\mathbf{N}$ 和 $\mathbf{L}$，分别表示 $\mathbf{G}$ 中字符串数量，以及 $\mathbf{B}$ 和 $\mathbf{G}$ 中字符串的长度。第二行为 $\mathbf{N}$ 个长度为 $\mathbf{L}$ 的不同字符串，表示 $\mathbf{G}$。第三行为一个长度为 $\mathbf{L}$ 的字符串，表示不良字符串 $\mathbf{B}$。$\mathbf{B}$ 和 $\mathbf{G}$ 中所有字符串仅由 $\mathbf{0}$ 和 $\mathbf{1}$ 组成。

对于每组测试用例，若无法满足条件，输出一行 `Case #x: IMPOSSIBLE`，否则输出一行 `Case #x: y z`，其中 $\mathbf{x}$ 为测试用例编号（从 1 开始），$\mathbf{y}$ 和 $\mathbf{z}$ 是你构造的两段程序。两段程序的总指令数不得超过 200，每段程序至少包含一条指令，且两段程序中 $\mathbf{?}$ 指令总数恰好为 $\mathbf{L}$。

**样例解释** 样例输出展示了一组可能答案，其他答案也可能是正确的。 样例第 1 组即为题面中的例子。 样例第 2 组不会出现在小数据集中。 样例第 3 组显然 IMPOSSIBLE，因为 $\mathbf{B}$ 就在 $\mathbf{G}$ 中。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 100$。 - $1 \leqslant \mathbf{N} \leqslant 100$。 - $1 \leqslant \mathbf{L} \leqslant 50$。 - $\mathbf{G}$ 中所有字符串均不同。 **小数据集（7 分，测试集 1 - 可见）** - $\mathbf{B}$ 全部由 $\mathbf{1}$ 组成。 **大数据集（28 分，测试集 2 - 隐藏）** - $\mathbf{B}$ 可以是任意由 $\mathbf{0}$ 和/或 $\mathbf{1}$ 组成的字符串。 翻译由 GPT4.1 完成。