Gnalcats#9705
Дослідники виявили нову форму життя, яку вони назвали Gnalcats. У Gnalcats дуже незвичайна структура ДНК і білків, проте дослідникам вдалося зрозуміти, як вони працюють. Тепер вони намагаються класифікувати види Gnalcats, порівнюючи їхню ДНК.
Ген їхньої ДНК являє собою послідовність основ. Ці гени діють на білки, які є надзвичайно довгими ланцюжками амінокислот \big(a - b - c - \ldots\big). Амінокислоти бувають простими та складними (що складаються з двох інших амінокислот). Білки завжди містять кілька мільярдів амінокислот.
Гени діють на білки наступним чином: семи різним основам (C, D, L, P, R, S, U) відповідають різні перетворення білка. Результат застосування гена до білка отримується послідовним застосуванням перетворень, що відповідають окремим основам гена: перша основа гена перетворює вихідний білок, потім до отриманого білка застосовується перетворення, що відповідає другій основі гена, і так далі. Життя недосконале, тому одне з цих перетворень може завершитися невдачею, і в цьому випадку все перетворення вважається неуспішним. Якщо на якомусь етапі перетворення білок скорочується до ланцюжка з трьох або менше амінокислот (простих чи складних), перетворення також завершується невдачею.
Дія кожної основи описана в наступній таблиці, де позначає хвіст білка, а і — амінокислоти (прості або складні):
Base | Input protein | Output protein |
C | a - X | a - a - X |
D | a - X | |
L | a - X | \left\{ \begin{array}{ll} b - X & \text{if } a \text{ is the complex amino-acid } <b,c>\\ \text{fail} & \text{if } a \text{ is a simple amino-acid} \end{array} \right. |
P | a - b - X | c - X, where is the complex amino-acid <a,b> |
R | a - X | \left\{ \begin{array}{ll} c - X & \text{if } a \text{ is the complex amino-acid } <b,c>\\ \text{fail} & \text{if } a \text{ is a simple amino-acid} \end{array} \right. |
S | a - b - X | b - a - X |
U | a - X | \left\{ \begin{array}{ll} b - c - X & \text{if } a \text{ is the complex amino-acid } <b,c>\\ \text{fail} & \text{if } a \text{ is a simple amino-acid} \end{array} \right. |
Наприклад, ген PSDSPCRPSDUL перетворює білок наступним чином:
вихідний білок має вигляд a - b - c - d - e - f - \ldots
застосування правила для першої дає: <a, b> - c - d - e - f - \ldots
застосування правила для дає: c - <a, b> - d - e - f - \ldots
дає: <a, b> - d - e - f - \ldots
дає: d - <a, b> - e - f - \ldots
дає: <d, <a, b>> - e - f - \ldots
дає: <d, <a, b>> - <d, <a, b>> - e - f - \ldots
дає: <a, b> - <d, <a, b>> - e - f - \ldots
дає: <<a, b>, <d, <a, b>>> - e - f - \ldots
дає: e - <<a, b>, <d, <a, b>>> - f - \ldots
дає: <<a, b>, <d, <a, b>>> - f - \ldots
дає: <a, b> - <d, <a, b>> - f - \ldots
нарешті, дає: a - <d, <a, b>> - f - \ldots
Вам дано два гени. Необхідно визначити, чи є вони еквівалентними. Два гени називаються еквівалентними, якщо для будь-якого вхідного білка, що складається з щонайменше одного мільярда простих амінокислот, виконується одна з двох умов: або застосування обох генів дає однаковий вихідний білок, або обидва застосування завершуються невдачею.
Містить два рядки, кожен з яких представляє один ген Gnalcats. Кожен ген містить хоча б одну основу. Сумарна довжина двох вхідних генів не перевищує 10^4.
Виведіть одне слово: True, якщо гени еквівалентні, та False у протилежному випадку.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Приклад 5