Задача №114537. Изменённая ДНК
Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов « A », « G », « C » и « T ».
Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответствующий символ. Например, последовательность « AAAGGTCCA » в закодированной форме имеет вид « 3A2GT2CA ».
В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.
Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.
Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.
В единственной строке входа находится строка \(s\), состоящая из цифр и букв « A », « G », « C » и « T » — закодированная ДНК.
Гарантируется, что это строка является корректной закодированной записью некоторой строки из символов « A », « G », « C » и « T ».
В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:
-
[noitemsep,leftmargin=2cm]
- 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 | 9 | \(1 \le n \le L \le 10\) | полная | |
| 2 | 17 | \(1 \le n \le 100\), \(1 \le L \le {10}^4\) | 1 | первая ошибка |
| 3 | 21 | \(1 \le n \le 1000\), \(1 \le L \le {10}^5\) | 1, 2 | первая ошибка |
| 4 | 11 | \(1 \le n \le {10}^5\), \(1 \le L \le {10}^7\) | 1–3 | первая ошибка |
| 5 | 42 | \(1 \le n \le {10}^5\), \(1 \le L \le {10}^9\) | 1–4 | первая ошибка |
Исходная последовательность имела вид « AAAAACAAAAACC ».
Первая операция превращает её в последовательность « AAAAAAAAAAACC », которая кодируется как « 11A2C ». Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную \(5\).
Вторая операция превращает её в последовательность « AACAAACAAAAACC », которая кодируется как « 2AC3AC5A2C ». Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную \(10\).
5AC5A2C
2 6 1 2 C