|
Изменённая ДНК
(Время: 1 сек. Память: 16 Мб Сложность: 57%)
Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов «A», «G», «C» и «T».
Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответствующий символ. Например, последовательность «AAAGGTCCA» в закодированной форме имеет вид
«3A2GT2CA».
В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.
Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.
Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.
Входные данные
В единственной строке входного файла INPUT.TXT находится строка s, состоящая из цифр и букв «A», «G», «C» и «T» — закодированная ДНК.
Гарантируется, что это строка является корректной закодированной записью некоторой строки
из символов «A», «G», «C» и «T».
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:
- 1 x Z, если надо вставить символ Z так, чтобы слева от него было ровно x старых символов. Символ Z должен быть из множества {A, C, G, T}.
- 2 x, если надо удалить символ с номером x из последовательности.
- 3 x Z, если надо заменить символ с номером x заменить на символ Z. Символ Z должен быть из множества {A, C, G, T}. При этом на этом месте до мутации обязательно должен был находиться символ, не равный Z.
В следующей строке выведите мутацию, после которой закодированная строка имеет максимальную длину, в таком же формате.
Если подходящих ответов несколько, можно вывести любой из них.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5AC5A2C | 3 6 A 1 2 C |
Пояснение к примеру
Исходная последовательность имела вид «AAAAACAAAAACC».
Первая операция превращает её в последовательность «AAAAAAAAAAACC», которая кодируется как «11A2C». Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную 5.
Вторая операция превращает её в последовательность «AACAAACAAAAACC», которая кодируется как «2AC3AC5A2C». Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную 10.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |