Gnalcats

연구자들은 Gnalcats라는 새로운 생명체를 발견했다. Gnalcats는 매우 독특한 형태의 DNA와 단백질을 가지지만, 연구자들은 그 작동 방식을 밝혀냈다. 이제 연구자들은 DNA를 비교해 Gnalcats의 종을 분류하려고 한다.

Gnalcats의 DNA에서 유전자는 염기 서열이다. 이 유전자는 단백질을 변형한다. 단백질은 아미노산이 아주 길게 이어진 사슬이다(a − b − c − . . .). 아미노산은 단순하거나 복합적이다(복합 아미노산은 다른 두 아미노산으로 이루어진다). 단백질은 항상 수십억 개의 아미노산을 포함한다.

유전자는 다음과 같은 방식으로 단백질을 변형한다. 일곱 개의 서로 다른 염기(C, D, L, P, R, S, U)는 단백질에 대한 서로 다른 변환에 대응한다. 유전자를 단백질에 적용한 결과는 유전자의 각 염기에 해당하는 개별 변환을 차례로 조합한 것이다. 즉, 유전자의 첫 번째 염기가 입력 단백질을 변환하고, 그 결과 단백질을 두 번째 염기의 규칙에 따라 변환하는 식으로 이어진다. 세상은 완벽하지 않기에 이러한 변환 중 하나가 실패할 수 있으며, 그 경우 전체 변환이 실패한다. 변환이 진행되는 어느 시점에서든 단백질이 세 개 이하의 아미노산(단순 또는 복합)으로 이루어진 사슬로 줄어들면 변환은 실패한다.

각 염기의 효과는 다음 표에 나와 있다. 여기서 X는 단백질의 나머지 부분을 나타내고, a, b, c는 아미노산(단순 또는 복합)이다.

예를 들어 유전자 PSDSPCRPSDUL은 단백질을 다음과 같이 변환한다.

• 입력 단백질은 a − b − c − d − e − f − . . .
• 첫 번째 P의 규칙을 적용하면 <a, b> − c − d − e − f − . . .
• 다음 S의 규칙을 적용하면 c − <a, b> − d − e − f − . . .
• 다음 D를 적용하면 <a, b> − d − e − f − . . .
• 다음 S를 적용하면 d − <a, b> − e − f − . . .
• 다음 P를 적용하면 <d,<a, b>> − e − f − . . .
• 다음 C를 적용하면 <d,<a, b>> − <d,<a, b>> − e − f − . . .
• 다음 R을 적용하면 <a, b> − <d,<a, b>> − e − f − . . .
• 다음 P를 적용하면 <<a, b>,<d,<a, b>>> − e − f − . . .
• 다음 S를 적용하면 e − <<a, b>,<d,<a, b>>> − f − . . .
• 다음 D를 적용하면 <<a, b>,<d,<a, b>>> − f − . . .
• 다음 U를 적용하면 <a, b> − <d,<a, b>> − f − . . .
• 마지막으로 L을 적용하면 a − <d,<a, b>> − f − . . .

두 유전자가 주어졌을 때, 두 유전자가 동등한지 판별해야 한다. 두 유전자는, 적어도 십억 개의 단순 아미노산으로 이루어진 모든 입력 단백질에 대해 두 유전자를 적용한 결과가 같은 단백질을 만들거나 둘 다 실패할 때 동등하다.

입력은 두 줄로 이루어지며, 각 줄은 Gnalcats 유전자 하나를 나타낸다.

한 단어를 출력한다. 두 유전자가 동등하면 “True”, 그렇지 않으면 “False”를 출력한다.

각 유전자는 하나 이상의 염기를 포함한다. 입력 유전자의 길이의 합은 10^4 이하이다.