{"problem":{"name":"D. Gnalcats","description":{"content":"A gene of their DNA is a sequence of bases. These genes operate on proteins, which are extremely long chains of amino-acids ($a -b -c -\\\\dots$). Amino-acids are either simple or complex (composed of t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10250D"},"statements":[{"statement_type":"Markdown","content":"A gene of their DNA is a sequence of bases. These genes operate on proteins, which are extremely long chains of amino-acids ($a -b -c -\\\\dots$). Amino-acids are either simple or complex (composed of two other amino-acids). Proteins always contain several billions of amino-acids.\n\nGenes 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.\n\nThe effect of each base is described in the following table where $X$ denotes the tail of the protein, while $a$, $b$, and $c$ are amino-acids (either simple or complex):\n\n$$ \\begin{array}{c r l} \\hline \\text{base} & \\text{input protein} & \\text{output protein} \\\\ \\hline \\textbf{C} & a-X & a-a-X\\\\ \\textbf{D} & a-X & X\\\\ \\textbf{L} & a-X & \\left\\{\\begin{array}{l l} b-X & \\text{if $a$ is the complex amino-acid $\\langle b, c\\rangle$} \\\\ \\text{fail} & \\text{if $a$ is a simple amino-acid} \\end{array}\\right. \\\\ \\textbf{P} & a-b-X & c-X \\text{ where $c$ is the complex amino-acid $\\langle a, b\\rangle$}\\\\ \\textbf{R} & a-X & \\left\\{\\begin{array}{l l} c-X & \\text{if $a$ is the complex amino-acid $\\langle b, c\\rangle$} \\\\ \\text{fail} & \\text{if $a$ is a simple amino-acid} \\end{array}\\right. \\\\ \\textbf{S} & a-b-X & b-a-X\\\\ \\textbf{U} & a-X & \\left\\{\\begin{array}{l l} b-c-X & \\text{if $a$ is the complex amino-acid $\\langle b, c\\rangle$} \\\\ \\text{fail} & \\text{if $a$ is a simple amino-acid} \\end{array}\\right. \\\\ \\hline \\end{array} $$\n\nFor example, the gene *PSDSPCRPSDUL* transforms a protein like this: \n\nYou are given two genes, and you must decide whether they are equivalent. Two genes are equivalent if for every input protein composed of at least one billion of simple amino-acids, either the application of both genes produces the same output protein, or both applications fail.\n\nThe input consists of two lines, each representing a Gnalcats gene.\n\n*Limits*\n\nEach gene contains at least one base. The sum of the length of the input genes is not greater than $10^4$.\n\nThe output consists of a single word: \"True\" if the genes are equivalent, \"False\" otherwise.\n\n*Sample Explanation 1*\n\nThese genes do nothing: they always transform a protein into the exact same protein.\n\n*Sample Explanation 2*\n\nThese genes always fail because both *L* and *R* bases fail on simple amino acids.\n\n## Input\n\nThe input consists of two lines, each representing a Gnalcats gene.*Limits*Each gene contains at least one base. The sum of the length of the input genes is not greater than $10^4$.\n\n## Output\n\nThe output consists of a single word: \"True\" if the genes are equivalent, \"False\" otherwise.\n\n[samples]\n\n## Note\n\n*Sample Explanation 1*These genes do nothing: they always transform a protein into the exact same protein.*Sample Explanation 2*These genes always fail because both *L* and *R* bases fail on simple amino acids.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ E $ be a set of employees, where each employee $ e \\in E $ is a triple $ (T, N, K) $:  \n- $ T \\in \\{\\text{Sir}, \\text{Madam}, \\text{Miss}, \\text{Honorable}, \\text{Heneral}, \\text{Ginoong}, \\text{Ginang}, \\text{Binibining}, \\text{Lolo}, \\text{Lola}, \\text{Ninong}, \\text{Ninang}, \\text{Darth}\\} $ is the title,  \n- $ N \\in \\Sigma^* $ is the name ($1 \\le |N| \\le 13$, alphabetic, capitalized first letter),  \n- $ K \\in \\Sigma^* $ is the nickname ($1 \\le |K| \\le 13$, alphabetic, capitalized first letter).  \n\nLet $ \\text{nameMap}: \\Sigma^* \\to E $ map each name to its employee.  \nLet $ \\text{nickMap}: \\Sigma^* \\to E $ map each nickname to its employee.  \n\nLet $ S \\subseteq E $ be the set of employees currently inside the factory premises. Initially, $ S = \\emptyset $.  \n\nLet $ L = [l_1, l_2, \\dots, l_n] $ be a sequence of log entries in chronological order, where each $ l_i $ is one of:  \n- $ \\text{IN } T \\ N $: employee with title $ T $ and name $ N $ enters,  \n- $ \\text{IN } K $: employee with nickname $ K $ enters,  \n- $ \\text{OUT } T \\ N $: employee with title $ T $ and name $ N $ exits,  \n- $ \\text{OUT } K $: employee with nickname $ K $ exits,  \n- $ \\text{UNION} $: record the size of $ S $,  \n- $ \\text{FIND } T \\ N $: query whether the employee with title $ T $ and name $ N $ is in $ S $,  \n- $ \\text{FIND } K $: query whether the employee with nickname $ K $ is in $ S $.  \n\n**Constraints**  \n- $ 1 \\le |E| \\le 10^5 $  \n- $ 1 \\le n \\le 10^5 $  \n- All names and nicknames in log entries are guaranteed to exist in $ E $.  \n- No two employees share the same name or nickname.  \n\n**Objective**  \nFor each log entry $ l_i \\in L $:  \n- If $ l_i = \\text{UNION} $, output $ |S| $.  \n- If $ l_i = \\text{FIND } T \\ N $, output $ \\text{FOUND} $ if $ \\text{nameMap}[N] \\in S $, else $ 404 $.  \n- If $ l_i = \\text{FIND } K $, output $ \\text{FOUND} $ if $ \\text{nickMap}[K] \\in S $, else $ 404 $.  \n- For $ \\text{IN } T \\ N $ or $ \\text{IN } K $: add the corresponding employee to $ S $.  \n- For $ \\text{OUT } T \\ N $ or $ \\text{OUT } K $: remove the corresponding employee from $ S $.  \n\nOutput results for UNION and FIND queries in chronological order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10250D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}