P15187 [SWERC 2019] Gnalcats

研究人员发现了一种新的生命形式，将其命名为 Gnalcats。Gnalcats 的 DNA 和蛋白质形式非常奇特，但研究人员已经理解了它们的工作原理。他们现在试图通过比较 DNA 来对 Gnalcats 的物种进行分类。 其 DNA 中的一个基因是一个碱基序列。这些基因作用于蛋白质，蛋白质是极长的氨基酸链（$a - b - c - \ldots$）。氨基酸有的是简单的，有的是复杂的（由两个其他氨基酸组成）。蛋白质通常包含数十亿个氨基酸。 基因按以下方式作用于蛋白质：七种不同的碱基（C、D、L、P、R、S、U）对应蛋白质上的不同变换。基因对蛋白质的操作结果由基因中每个碱基的单独变换组合而成：基因的第一个碱基变换输入蛋白质，得到的蛋白质再根据基因的第二个碱基进行变换，依此类推。生命并不完美，因此这些变换中可能会有一个失败，此时整个变换失败。如果在变换的任何时刻，蛋白质被简化为三个或更少氨基酸（简单或复杂）的链，则变换失败。 每种碱基的作用如下表所示，其中 $X$ 表示蛋白质的尾部，而 $a$、$b$ 和 $c$ 是氨基酸（简单或复杂）： | 碱基 | 输入蛋白质 | 输出蛋白质 | |:-:|:-:|:-:| | **C** | $a - X$ | $a - a - X$ | | **D** | $a - X$ | $X$ | | **L** | $a - X$ | $\begin{cases} b - X & \text{如果 } a \text{ 是复杂氨基酸 } (b,c) \\ \text{失败} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$ | | **P** | $a - b - X$ | $c - X$，其中 $c$ 是复杂氨基酸 $(a,b)$ | | **R** | $a - X$ | $\begin{cases} c - X & \text{如果 } a \text{ 是复杂氨基酸 } (b,c) \\ \text{失败} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$ | | **S** | $a - b - X$ | $b - a - X$ | | **U** | $a - X$ | $\begin{cases} b - c - X & \text{如果 } a \text{ 是复杂氨基酸 } (b,c) \\ \text{失败} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$ | 例如，基因 **PSDPCRPSDUL** 按以下方式变换蛋白质： - 输入蛋白质为 $a - b - c - d - e - f - \ldots$ - 应用第一个 **P** 的规则得到：$(a,b) - c - d - e - f - \ldots$ - 应用 **S** 的规则得到：$c - (a,b) - d - e - f - \ldots$ - **D** 得到：$(a,b) - d - e - f - \ldots$ - **S** 得到：$d - (a,b) - e - f - \ldots$ - **P** 得到：$(d, (a,b)) - e - f - \ldots$ - **C** 得到：$(d, (a,b)) - (d, (a,b)) - e - f - \ldots$ - **R** 得到：$(a,b) - (d, (a,b)) - e - f - \ldots$ - **P** 得到：$((a,b), (d, (a,b))) - e - f - \ldots$ - **S** 得到：$e - ((a,b), (d, (a,b))) - f - \ldots$ - **D** 得到：$((a,b), (d, (a,b))) - f - \ldots$ - **U** 得到：$(a,b) - (d, (a,b)) - f - \ldots$ - 最后 **L** 得到：$a - (d, (a,b)) - f - \ldots$ 给定两个基因，你需要判断它们是否等价。两个基因等价当且仅当对于每一个由**至少十亿个简单氨基酸**组成的输入蛋白质，要么两个基因的应用产生相同的输出蛋白质，要么两个应用都失败。

输入包含两行，每行表示一个 Gnalcats 基因。

输出包含一个单词：如果基因等价，输出 **True**；否则输出 **False**。

#### 样例解释 1 这些基因不做任何操作：它们总是将蛋白质变换为完全相同的蛋白质。 #### 样例解释 2 这些基因总是失败，因为 L 和 R 碱基在简单氨基酸上都会失败。 #### 数据范围 每个基因至少包含一个碱基。输入基因的长度总和不超过 $10^4$。 翻译由 DeepSeek 完成