Генетика
Колонія інопланетних бактерій була нещодавно виявлена біля кратера в Нью-Мексико. Доктор Пуше очолює наукову команду в ICPC BioLab, яка досліджує структуру їхньої інопланетної ДНК. Ось короткий виклад їхніх відкриттів.
Молекули інопланетної ДНК мають форму кругової послідовності, що складається з нуклеотидів. Існує 26 різних типів нуклеотидів, і кожен з них може існувати у двох формах. Важливо зазначити, що в будь-якій даній молекулі інопланетної ДНК кожен нуклеотид або відсутній, або зустрічається рівно двічі (тому довжина молекули ДНК завжди парна і знаходиться в діапазоні від 2 до 52). Якщо нуклеотид зустрічається двічі, кожна його поява може бути в будь-якій формі незалежно. Інопланетні бактерії мають два типи кінцівок, які в біологічній термінології називаються руками і ногами. Головне відкриття команди доктора Пуше — це метод визначення точної кількості рук і ніг бактерії за структурою її ДНК.
Кожен нуклеотид представлений літерою алфавіту. Ми позначаємо різні нуклеотиди як a, A, . . . z, Z, де малі і великі форми літери представляють собою дві можливі форми нуклеотиду; ми також будемо використовувати a/A, b/B, . . . z/Z для позначення нуклеотиду в будь-якій формі.
Щоб визначити кількість кінцівок, доктор Пуше починає з ініціалізації двох лічильників для рук і ніг, встановлюючи їх у нуль, а потім виконує ряд операцій, перетворюючи послідовність ДНК. Після кожного перетворення, можливо, знадобиться збільшити деякі з лічильників, залежно від типу застосованої операції. Коли послідовність нуклеотидів стає порожньою (позначається як ∅), кількість кінцівок вихідної молекули буде знайдено. Можливі операції:
1. Видалення послідовних входжень даного нуклеотиду, що з'являється в протилежних формах. Кількість рук і ніг зберігається. Наприклад: aBbCaC → aCaC шляхом видалення Bb. Інший приклад: DeHhEd → eHhE шляхом видалення dD. Пам'ятайте, що структура ДНК є круговою, тому останні і перші літери з'єднані.
2. Видалення послідовних нуклеотидів, що з'являються в одній і тій же формі. Збільшіть кількість рук на одиницю. Наприклад: BBcgCg → cgCg шляхом видалення BB. Інший приклад: xabyyaBX → xabaBX шляхом видалення yy.
3. Видалення послідовності з чотирьох нуклеотидів, утвореної двома різними нуклеотидами, які з'являються почергово, де різні входження одного і того ж нуклеотиду мають протилежні форми. Збільшіть кількість ніг на одиницю. Наприклад: dcDCefFe → efFe, шляхом видалення dcDC. Інший приклад: cmNMnC → cC шляхом видалення mNMn.
4. Вирізання і вставка, найскладніша процедура.
Спочатку вибирається нуклеотид, наприклад a/A, і послідовність ДНК розрізається на дві лінійні ланцюги так, щоб нуклеотид з'являвся один раз у кожній з них.
По-друге, якщо обидва входження a/A мають одну і ту ж форму, один з ланцюгів "інвертується" шляхом реверсування послідовності і зміни форми кожного нуклеотиду в ланцюзі.
Потім ланцюги об'єднуються шляхом конкатенації підпослідовності, що з'являється перед a, з підпослідовністю, що з'являється після A, і підпослідовності, що з'являється після a, з підпослідовністю, що з'являється перед A.
Нарешті, два нових нуклеотиди a/A додаються для замикання ланцюга в кругову форму. Форма нових нуклеотидів така ж, якщо вихідна пара вибраних нуклеотидів мала одну і ту ж форму, і відрізняється в іншому випадку.
Формально, припустимо, що ви вибрали нуклеотид a/A, і далі припустимо на даний момент, що він з'являється обидва рази з формою a (A). Операція вирізання і вставки перетворює послідовності виду S_1aS_2S_3aS_4 (відповідно S_1AS_2S_3AS_4) в S_2aS_1S_3aS_4 (відповідно S_2AS_1S_3AS_4). З іншого боку, якщо нуклеотид a/A з'являється у двох різних формах, операція перетворює послідовності виду S_1aS_2S_3AS_4 в S_2aS_1S_4AS_3. S_1, S_2, S_3 і S_4 — довільні підланцюги (можливо, порожні). В обох випадках вихідний круговий ланцюг був розрізаний на S_1(a/A)S_2 і S_3(a/A)S_4.
Наприклад (див. рисунок нижче): починаючи з послідовності BacDcAbD, ми можемо отримати ланцюги BacDc і AbD. Потім, об'єднуючи по нуклеотиду a/A, ми отримуємо послідовність cDca’BbDA’, де a’ і A’ представляють нові нуклеотиди a/A. Тут S_1 = B, S_2 = cDc, S_3= ∅ і S_4= bD.
Інший приклад: візьмемо ту ж послідовність ДНК BacDcAbD, і розріжемо, щоб отримати ланцюги DBac і DcAb; вставте нуклеотид c/C (в цьому випадку вам потрібно інвертувати один ланцюг, наприклад BaCd), щоб отримати послідовність cDBadcBa. Тут S_1 = DBa, S_2 = ∅, S_3 = D і S_4 = Ab.
Ця операція не змінює кількість рук або ніг, але може бути використана вміло в поєднанні з попередніми операціями для зменшення розміру молекули ДНК і завершення розрахунку.
Однак інопланетні бактерії не мають одночасно і рук, і ніг. Це пов'язано з тим, що на ранніх стадіях розвитку нога в присутності однієї або кількох рук перетворюється в дві руки. Через вищезазначене кінцевий результат — це або кількість рук, або кількість ніг, але не одночасно. Щоб уникнути дорогих хірургічних процедур, доктор Пуше найняв вас для написання програми, яка обчислює кількість рук і ніг, які розвинуться у бактерії, виходячи з її послідовності ДНК. Гарантується, що результат визначається однозначно вихідним рядком, незалежно від конкретної послідовності застосованих операцій.
Вхідні дані
Кожен тестовий випадок складається з рядка парної довжини від 2 до 52 включно, що представляє структуру ДНК інопланетної бактерії. Всі символи є літерами. Вхід закінчується рядком "END", який обробляти не потрібно.
Вихідні дані
Вивід для кожного тестового випадку повинен містити рівно один рядок, що містить кількість рук або ніг, які будуть у бактерії, за яким слідує слово "arms" або "legs" відповідно (якщо кількість дорівнює 1, слова повинні бути в однині). У випадку, якщо не буде ні рук, ні ніг, програма повинна вивести слово "none".