QOJ.ac

QOJ

Límite de tiempo: 0.3 s Límite de memoria: 2048 MB Puntuación total: 100

#2650. Gnalcats

Estadísticas

研究人员发现了一种新的生命形式,他们将其命名为 Gnalcats。Gnalcats 的 DNA 和蛋白质形式非常奇特,但研究人员已经理解了它们的工作原理。他们现在正试图通过比较 DNA 来对 Gnalcats 的物种进行分类。

它们的 DNA 中的一个基因是一串碱基序列。这些基因作用于蛋白质,蛋白质是极长的氨基酸链($a - b - c - \dots$)。氨基酸要么是简单的,要么是复杂的(由另外两个氨基酸组成)。蛋白质总是包含数十亿个氨基酸。

基因通过以下方式作用于蛋白质:七种不同的碱基(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{ 是复杂氨基酸 } \langle b, c \rangle \\ \text{fail} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$
P $a - b - X$ $c - X \text{ 其中 } c \text{ 是复杂氨基酸 } \langle a, b \rangle$
R $a - X$ $\begin{cases} c - X & \text{如果 } a \text{ 是复杂氨基酸 } \langle b, c \rangle \\ \text{fail} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$
S $a - b - X$ $b - a - X$
U $a - X$ $\begin{cases} b - c - X & \text{如果 } a \text{ 是复杂氨基酸 } \langle b, c \rangle \\ \text{fail} & \text{如果 } a \text{ 是简单氨基酸} \end{cases}$

你需要判断给定的两个基因是否等价。如果对于每个由至少十亿个简单氨基酸组成的输入蛋白质,两个基因的应用要么产生相同的输出蛋白质,要么都失败,则称这两个基因是等价的。

输入格式

输入包含两行,每一行代表一个 Gnalcats 基因。

数据范围

每个基因至少包含一个碱基。输入基因的长度之和不超过 $10^4$。

输出格式

输出为一个单词:“True”(如果基因等价)或“False”(否则)。

样例

样例输入 1

PU
SS

样例输出 1

True

说明 1

这些基因什么都不做:它们总是将蛋白质转化为完全相同的蛋白质。

样例输入 2

L
R

样例输出 2

True

说明 2

这些基因总是失败,因为 L 和 R 碱基在简单氨基酸上都会失败。

样例输入 3

PSPCRSL
PS

样例输出 3

True

样例输入 4

U
C

样例输出 4

False

样例输入 5

PL
PR

样例输出 5

False

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.