Преобразование ДНК
(Время: 1 сек. Память: 16 Мб Сложность: 36%)
Для начала заметим, что поскольку, по условию, решение всегда существует, то количество букв каждого вида в первой строке равно количеству букв этого же вида во второй строке. Будем решать задачу следующим образом. Пусть мы добились того, что первые k букв исходной последовательности ДНК после применения необходимых преобразований (обозначим ее s1) совпадают с первыми k буквами требуемой последовательности ДНК (обозначим ее s2).
Разберем, как добиться того, чтобы после применения одного преобразования совпадали первые k+1 букв. Для этого выберем букву, стоящую на позиции j, что j > k и s1[j] = s2[k+1] и применим преобразование c k+1 по j-й символ к строке s1. Понятно, что после этого у строк s1 и s2 будут совпадать первые k+1 букв. Таким образом, мы сможем не более чем за l−1 (где l – это длина последовательности ДНК) операций преобразовать исходную последовательность ДНК в требуемую.
Будем считать, что процедура reverse(i, j) производит разворот фрагмента строки s1 с i-го по j-й символ и выводит в выходной файл соответствующую информацию. Приведем основной фрагмент алгоритмической реализации данной задачи:
for i=1..l-1
for j=i..l
if(s1[i]=s2[j]){
reverse(i,j)
break
}
Разбор: Александр Торопов.
|