| Автор: | Олег Христенко | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Биологи обнаружили новый живой организм и решили изучить его ДНК.
ДНК кодируется последовательностью символов
"A", "G", "C" и "T".
Так как строка, кодирующая ДНК, часто очень длинная,
для её хранения применяют RLE-кодирование.
А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов,
заменяется на число, равное длине этого блока,
после которого записывается соответствующий символ.
Например, последовательность "AAAGGTCCA" в закодированной форме имеет вид
"3A2GT2CA".
В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.
Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.
Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.
В единственной строке входа находится строка s, состоящая из цифр и букв
"A", "G", "C" и "T" — закодированная ДНК.
Гарантируется, что это строка является корректной закодированной записью
некоторой строки из символов
"A", "G", "C" и "T".
В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:
1 x Z, если надо вставить символ Z так,
чтобы слева от него было ровно x старых символов.
Символ Z должен быть из множества
{A, C, G, T}.2 x, если надо удалить символ с номером x из последовательности.3 x Z, если надо заменить символ с номером x
на символ Z.
Символ Z должен быть из множества
{A, C, G, T}.
При этом на этом месте до мутации обязательно должен был находиться символ,
не равный Z.В следующей строке выведите мутацию, после которой закодированная строка имеет максимальную длину, в таком же формате.
Если подходящих ответов несколько, можно вывести любой из них.
Обозначим за n длину закодированной строки, а за L длину исходной строки.
1 ≤ n ≤ 105, 1 ≤ L ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 9 | 1 ≤ n ≤ L ≤ 10 | полная | |
| 2 | 17 | 1 ≤ n ≤ 100, 1 ≤ L ≤ 104 | 1 | первая ошибка |
| 3 | 21 | 1 ≤ n ≤ 1000, 1 ≤ L ≤ 105 | 1, 2 | первая ошибка |
| 4 | 11 | 1 ≤ n ≤ 105, 1 ≤ L ≤ 107 | 1--3 | первая ошибка |
| 5 | 42 | 1 ≤ n ≤ 105, 1 ≤ L ≤ 109 | 1--4 | первая ошибка |
Исходная последовательность имела вид "AAAAACAAAAACC".
Первая операция превращает её в последовательность "AAAAAAAAAAACC",
которая кодируется как "11A2C".
Эта закодированная последовательность имеет минимальную возможную для этого теста длину,
равную 5.
Вторая операция превращает её в последовательность "AACAAACAAAAACC",
которая кодируется как "2AC3AC5A2C".
Эта закодированная последовательность имеет максимальную возможную для этого теста длину,
равную 10.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|