Gnalcats#9705
Researchers have discovered a new form of life they have named Gnalcats. Gnalcats have a very strange form of DNA and proteins, but the researchers have understood how they work. They are now trying to classify species of Gnalcats by comparing their DNA.
A gene of their DNA is a sequence of bases. These genes operate on proteins, which are extremely long chains of amino acids \big(a - b - c - \ldots\big). Amino acids are either simple or complex (composed of two other amino acids). Proteins always contain several billions of amino acids.
Genes operate on proteins in the following way: the seven different bases (C, D, L, P, R, S, U) correspond to different transformations on the protein. The result of the operation of a gene on a protein is obtained as the combination of the individual transformations by each base of the gene: the first base of the gene transforms the input protein, the resulting protein is then transformed according to the second base of the gene, and so on. Life is not perfect, and thus one of these transformations may fail, in which case the overall transformation fails. If, at any point in the transformation, the protein is reduced to a chain of three or fewer amino acids (simple or complex), then the transformation fails.
The effect of each base is described in the following table, where denotes the tail of the protein, and and are amino acids (either simple or complex):
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. |
For example, the gene PSDSPCRPSDUL transforms a protein as follows:
the input protein is a - b - c - d - e - f - \ldots
applying the rule for the first produces: <a, b> - c - d - e - f - \ldots
applying the rule for produces: c - <a, b> - d - e - f - \ldots
gives: <a, b> - d - e - f - \ldots
gives: d - <a, b> - e - f - \ldots
gives: <d, <a, b>> - e - f - \ldots
gives: <d, <a, b>> - <d, <a, b>> - e - f - \ldots
gives: <a, b> - <d, <a, b>> - e - f - \ldots
gives: <<a, b>, <d, <a, b>>> - e - f - \ldots
gives: e - <<a, b>, <d, <a, b>>> - f - \ldots
gives: <<a, b>, <d, <a, b>>> - f - \ldots
gives: <a, b> - <d, <a, b>> - f - \ldots
finally, gives: a - <d, <a, b>> - f - \ldots
You are given two genes and must decide whether they are equivalent. Two genes are equivalent if, for every input protein composed of at least one billion simple amino acids, either the application of both genes produces the same output protein, or both applications fail.
Consists of two lines, each representing a Gnalcats gene. Each gene contains at least one base. The sum of the lengths of both input genes does not exceed 10^4.
Print a single word: "True" if the genes are equivalent, and "False" otherwise.
Example 1
Example 2
Example 3
Example 4
Example 5