Генетика

Колонія інопланетних бактерій була нещодавно виявлена біля кратера в Нью-Мексико. Доктор Пуше очолює наукову команду в ICPC BioLab, яка досліджує структуру їхньої інопланетної ДНК. Ось короткий виклад їхніх відкриттів.

Молекули інопланетної ДНК мають форму кругової послідовності, що складається з нуклеотидів. Існує $26$ різних типів нуклеотидів, і кожен з них може існувати у двох формах. Важливо зазначити, що в будь-якій даній молекулі інопланетної ДНК кожен нуклеотид або відсутній, або зустрічається рівно двічі (тому довжина молекули ДНК завжди парна і знаходиться в діапазоні від $2$ до $52$). Якщо нуклеотид зустрічається двічі, кожна його поява може бути в будь-якій формі незалежно. Інопланетні бактерії мають два типи кінцівок, які в біологічній термінології називаються руками і ногами. Головне відкриття команди доктора Пуше — це метод визначення точної кількості рук і ніг бактерії за структурою її ДНК.

Кожен нуклеотид представлений літерою алфавіту. Ми позначаємо різні нуклеотиди як $\text{a}$, $\text{A}$, $\dots$, $\text{z}$, $\text{Z}$, де малі і великі форми літери представляють собою дві можливі форми нуклеотиду; ми також будемо використовувати $\text{a}/\text{A}$, $\text{b}/\text{B}$, $\dots$, $\text{z}/\text{Z}$ для позначення нуклеотиду в будь-якій формі.

Щоб визначити кількість кінцівок, доктор Пуше починає з ініціалізації двох лічильників для рук і ніг, встановлюючи їх у нуль, а потім виконує ряд операцій, перетворюючи послідовність ДНК. Після кожного перетворення, можливо, знадобиться збільшити деякі з лічильників, залежно від типу застосованої операції. Коли послідовність нуклеотидів стає порожньою (позначається як $\text{∅}$), кількість кінцівок вихідної молекули буде знайдено. Можливі операції:

$\text{1.}$ Видалення послідовних входжень даного нуклеотиду, що з'являється в протилежних формах. Кількість рук і ніг зберігається. Наприклад: \textbf{aBbCaC}\to\textbf{aCaC} шляхом видалення $\text{Bb}$. Інший приклад: \textbf{DeHhEd}\to\textbf{eHhE} шляхом видалення $\text{dD}$. Пам'ятайте, що структура ДНК є круговою, тому останні і перші літери з'єднані.

$\text{2.}$ Видалення послідовних нуклеотидів, що з'являються в одній і тій же формі. Збільште кількість рук на одиницю. Наприклад: \textbf{BBcgCg}\to\textbf{cgCg} шляхом видалення $\text{BB}$. Інший приклад: \textbf{xabyyaBX}\to\textbf{xabaBX} шляхом видалення $\text{yy}$.

$\text{3.}$ Видалення послідовності з чотирьох нуклеотидів, утвореної двома різними нуклеотидами, які з'являються почергово, де різні входження одного і того ж нуклеотиду мають протилежні форми. Збільште кількість ніг на одиницю. Наприклад: \textbf{dcDCefFe}\to\textbf{efFe}, шляхом видалення $\text{dcDC}$. Інший приклад: \textbf{cmNMnC}\to\textbf{cC} шляхом видалення $\text{mNMn}$.

$\text{4.}$ Вирізання і вставка, найскладніша процедура.

Спочатку вибирається нуклеотид, наприклад $\text{a}/\text{A}$, і послідовність ДНК розрізається на два лінійні ланцюги так, щоб нуклеотид з'являвся один раз у кожному з них.

По-друге, якщо обидва входження $\text{a}/\text{A}$ мають одну і ту ж форму, один з ланцюгів інвертується шляхом реверсування послідовності і зміни форми кожного нуклеотиду в ланцюзі.

Потім ланцюги об'єднуються шляхом конкатенації підпослідовності, що з'являється перед $a$, з підпослідовністю, що з'являється після $A$, і підпослідовності, що з'являється після $a$, з підпослідовністю, що з'являється перед $A$.

Нарешті, два нових нуклеотиди $\text{a}/\text{A}$ додаються для замикання ланцюга в кругову форму. Форма нових нуклеотидів така ж, якщо вихідна пара вибраних нуклеотидів мала одну і ту ж форму, і відрізняється в іншому випадку.

Формально, припустимо, що ви вибрали нуклеотид $\text{a}/\text{A}$, і далі припустимо на даний момент, що він з'являється обидва рази з формою $a$ ($A$). Операція вирізання і вставки перетворює послідовності виду \textbf{S}_1\textbf{a}\textbf{S}_2\textbf{S}_3\textbf{a}\textbf{S}_4 (відповідно \textbf{S}_1\textbf{A}\textbf{S}_2\textbf{S}_3\textbf{A}\textbf{S}_4) в \textbf{S}_2\textbf{a}\textbf{S}_1\textbf{S}_3\textbf{a}\textbf{S}_4 (відповідно \textbf{S}_2\textbf{A}\textbf{S}_1\textbf{S}_3\textbf{A}\textbf{S}_4). З іншого боку, якщо нуклеотид $\text{a}/\text{A}$ з'являється у двох різних формах, операція перетворює послідовності виду \textbf{S}_1\textbf{a}\textbf{S}_2\textbf{S}_3\textbf{A}\textbf{S}_4 в \textbf{S}_2\textbf{a}\textbf{S}_1\textbf{S}_4\textbf{A}\textbf{S}_3. \textbf{S}_1, \textbf{S}_2, \textbf{S}_3 і \textbf{S}_4 — довільні підланцюги (можливо, порожні). В обох випадках вихідний круговий ланцюг був розрізаний на \textbf{S}_1(\textbf{a}/\textbf{A})\textbf{S}_2 і \textbf{S}_3(\textbf{a}/\textbf{A})\textbf{S}_4.

Наприклад: починаючи з послідовності $\text{BacDcAbD}$, ми можемо отримати ланцюги $\text{BacDc}$ і $\text{AbD}$. Потім, об'єднуючи по нуклеотиду $\text{a}/\text{A}$, ми отримуємо послідовність $\text{cDca’BbDA’}$, де $\text{a’}$ і $\text{A’}$ представляють нові нуклеотиди $\text{a}/\text{A}$. Тут \textbf{S}_1 = \textbf{B}, \textbf{S}_2 = \textbf{cDc}, \textbf{S}_3 = \textbf{∅} і \textbf{S}_4 = \textbf{bD}.

Інший приклад: візьмемо ту ж послідовність ДНК $\text{BacDcAbD}$, і розріжемо, щоб отримати ланцюги $\text{DBac}$ і $\text{DcAb}$; вставте нуклеотид $\text{c}/\text{C}$ (в цьому випадку потрібно інвертувати один ланцюг, наприклад $\text{BaCd}$), щоб отримати послідовність $\text{cDBadcBa}$. Тут \textbf{S}_1 = \textbf{DBa}, \textbf{S}_2 = \textbf{∅}, \textbf{S}_3 = \textbf{D} і \textbf{S}_4 = \textbf{Ab}.

Ця операція не змінює кількість рук або ніг, але може бути використана в поєднанні з попередніми операціями для зменшення розміру молекули ДНК і завершення розрахунку.

Однак інопланетні бактерії не мають одночасно і рук, і ніг. Це пов'язано з тим, що на ранніх стадіях розвитку нога в присутності однієї або кількох рук перетворюється в дві руки. Через вище зазначене кінцевий результат — це або кількість рук, або кількість ніг, але не одночасно. Щоб уникнути дорогих хірургічних процедур, доктор Пуше найняв вас для написання програми, яка обчислює кількість рук і ніг, які розвинуться у бактерії, виходячи з її послідовності ДНК. Гарантується, що результат визначається однозначно вихідним рядком, незалежно від конкретної послідовності застосованих операцій.