Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Изменённая ДНК

(Время: 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.TXTOUTPUT.TXT
15AC5A2C3 6 A
1 2 C

Пояснение к примеру

Исходная последовательность имела вид «AAAAACAAAAACC».

Первая операция превращает её в последовательность «AAAAAAAAAAACC», которая кодируется как «11A2C». Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную 5.

Вторая операция превращает её в последовательность «AACAAACAAAAACC», которая кодируется как «2AC3AC5A2C». Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную 10.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Два станка
 B. Разбиение таблицы
 C. Изменённая ДНК
 D. Антенна
 E. Календарь на Альфе Центавра
 F. Числа
 G. Хорошие раскраски
 H. A+B

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



ставки на киберспорт cs