| Автор: | Олег Христенко | Ограничение времени: | 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 | |
|
Для того, чтобы получить минимальную длину, всегда выгодно удалить какой-то элемент, а чтобы получить максимальную длину, нужно добавить какой-то элемент. Докажем это.
Для минимума. Пусть мы заменили какой-то символ. Вместо этого удалим этот символ. Длина каждого из соседних блоков не изменится, либо они сольются в один. В любом случае длина закодированной строки получится меньше или такой же, как при замене. Аналогично, вместо добавления символа всегда выгоднее удалить символ перед ним.
Для максимума. Пусть мы заменили какой-то символ. Тогда вместо этого добавим в эту позицию тот символ, на который мы заменили. Длина каждого из соседних блоков не уменьшится, значит длина закодированной версии полученной строки будет не меньше. Аналогично вместо удаления символа всегда выгоднее добавить символ перед ним.
Перейдем теперь к рассмотрению того, как решить, какую именно операцию сделать.
Для того, чтобы решить первые две подзадачи, достаточно перебрать место, в которое нужно вставить новый элемент, или удалить существующий. После фиксирования изменения, можно посчитать длину закодированной строки полным проходом по ней. Асимптотика этого решения O(L2).
Для того, чтобы решить третью подзадачу, нужно заметить, что каждый блок одинаковых символов изменился не сильно. Поэтому после изменения символа достаточно для каждого исходного блока посчитать новую длину этого блока или новых блоков, которые появились после изменения. Асимптотика решения O(n ⋅ L).
Для того, чтобы решить четвертую подзадачу, нужно заметить, что после изменения меняется только блок, в котором произошло изменение, или соседние с ним блоки. Для всех остальных блоков длина не меняется, и её можно не пересчитывать. Асимптотика решения O(L).
Для того, чтобы решить пятую подзадачу, нужно научиться понимать, как правильно удалять и добавлять символы.
Если в строке есть блок длины 1, соседние блоки которого содержат одинаковые символы, то при удалении этого символа эти блоки объединятся в один, и длина закодированной строки уменьшится. Если в строке есть блок длины 1, то при его удалении длина строки уменьшится на 1. Если в строке есть блок длины 2, то при удалении символа из него, в его кодировке больше не нужно будет писать число, и длина строки уменьшится на 1. Если в строке есть блок длины 10x, то при удалении символа из него длина числа уменьшится на 1. Это все возможные способы уменьшения длины при удалении символа.
При добавлении символа можно поставить его в начало для создания нового блока длины 1, чтобы длина строки увеличилась на 1. Также можно какой-то блок разделить на два, если добавить другой символ внутри блока. Для блока длины до 20 достаточно перебрать, где именно будет новый символ. Если длина блока от 2 ⋅ 10x до 10x + 1, то из него можно выделить блок размера 10x, и увеличить длину строки на x + 3. Если длина блока от 10x + 10x − 1 до 2 ⋅ 10x, то из него можно выделить блок длины 10x, и увеличить длину строки на x + 2. Если длина блока от 10x до 10x + 10x − 1, то из него можно выделить блок длины 8 ⋅ 10x − 1, и увеличить длину строки на x + 1. Это все возможные способы увеличить длину строки при добавлении символа.
Для каждого блока проверим все оптимальные способы добавления и удаления символа и выберем оптимальный способ среди всех. Так как для каждого блока оптимальных способов всего O(1), то асимптотика решения O(n).