Школа программиста
Резервная копия - VPS Hoster 

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

HotLog


 

Преобразование ДНК

(Время: 1 сек. Память: 16 Мб Сложность: 36%)

Биологи лаборатории Advanced Cellular Mechanics Lab. (ACM Lab.) занимаются исследованиями в области геномов и ДНК. Недавно в этой лаборатории была разработана технология, позволяющая достаточно дешево производить с цепочкой ДНК некоторые преобразования.

Представим себе цепочку ДНК как строку длины N из символов из множества {A, G, C, T}. Элементарное преобразование, которое умеют проводить биологи лаборатории, представляет собой разворот подстроки с L-ого по R-ый символ (целые числа L и R выбираются так, что 1 ≤ L ≤ R ≤ N). Таким образом, из строки a1a2 ... aLaL+1 ... aR−1aR ... aN получается строка a1a2 ... aRaR−1 ... aL+1aL ... aN.

Теперь биологи разрабатывают аппаратно-программный комплекс для выполнения преобразований ДНК. Одной из его функций будет преобразование исходной цепочки ДНК в требуемую.

Ваша задача – написать программу, которая по исходной и требуемой цепочкам ДНК будет находить необходимую для этого цепочку элементарных преобразований.

Входные данные

Первая строка входного файла INPUT.TXT содержит описание исходной цепочки ДНК, вторая строка – описание требуемой цепочки ДНК. Длины обеих цепочек совпадают и не превышают 5000. Каждая из цепочек содержит только символы из множества {A, G, C, T}. Гарантируется, что искомая последовательность преобразований существует.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите количество K преобразований в построенном решении. Число K должно быть неотрицательным и не должно превышать 4999.

Далее выведите K строк, описывающих построенную последовательность элементарных преобразований. Каждая из строк должны содержать два числа: Li и Ri – соответственно левый и правый конец разворачиваемого на i-ом шаге отрезка.

Примеры

INPUT.TXTOUTPUT.TXT
1AGCT
GCAT
2
1 2
2 3
2AGCTA
ATCGA
1
1 5

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

[Обсуждение] [Все попытки] [Лучшие попытки]

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



Live ставки на mma