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

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


 

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

(Время: 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
    }

Разбор: Александр Торопов.

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


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