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

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

Представим себе цепочку ДНК как строку длины N из символов из множества {A, G, C, T}. Элементарное преобразование, которое умеют проводить биологи лаборатории, представляет собой разворот подстроки с L-ого по R-ый символ (целые числа L и R выбираются так, что 1 ≤ L ≤ R ≤ N). Таким образом, из строки a₁a₂ ... a_La_L+1 ... a_R−1a_R ... a_N получается строка a₁a₂ ... a_Ra_R−1 ... a_L+1a_L ... a_N.

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

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

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

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

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

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

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

Примеры

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

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