Генетика
Колония инопланетных бактерий была недавно обнаружена рядом с кратером в Нью-Мексико. Доктор Пуше возглавляет научную команду в 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".