e-olymp
Yarışlar

DFS + Cycles + Cactus

Понк Уоршалл

Слушание рок-музыки меняет вашу ядерную ДНК. Этот поразительный и невероятный факт был недавно опубликован в Rock Nature Weekly, одном из ведущих научных журналов на планете. Частью исследования было взятие образцов ДНК у добровольцев как до, так и после сезона рок-концертов. Образцы были обработаны, и из них были выделены различные гены. Для каждого человека каждый ген был выделен дважды: вариант до рок-сезона и вариант после сезона. Эти два варианта были парными, и во многих случаях было обнаружено, что один вариант представляет собой некоторую перестановку другого варианта в паре.

Следующим шагом в исследовании является определение того, как происходят перестановки. Преобладающая гипотеза предполагает, что перестановка состоит из последовательности транспозиций, так называемых обменов. Обмен - это событие (его химия еще полностью не изучена), при котором ровно два азотистых основания в гене меняются местами. Никакие другие азотистые основания гена обменом не затрагиваются. Положения двух замененных нуклеотидных оснований могут быть совершенно произвольными.

Чтобы предсказать и наблюдать движение молекул в процессе перестановки, исследователям необходимо знать теоретическое минимальное количество перестановок, которые могут привести к конкретной перестановке азотистых оснований в гене. Напоминаем, что ген ядерной ДНК представляет собой последовательность азотистых оснований цитозина, гуанина, аденина и тимина, которые кодируются как C, G, A и T соответственно.

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

Содержит две строки. Каждая строка содержит n заглавных букв "A", "C", "G" или "T" (1n106). Две строки представляют собой одну пару некоторых версий гена. Первая строка задает ген до рок-сезона, вторая строка задает тот же ген от того же человека после рок-сезона. Число вхождений каждого азотистого основания одинаково в обеих строках.

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

Выведите минимальное количество обменов, преобразующих первую версию гена во вторую.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
CGATA
ATAGC
Çıxış verilənləri #1
2
Giriş verilənləri #2
CTAGAGTCTA
TACCGTATAG
Çıxış verilənləri #2
7
Mənbə 2019 ACM Central Europe (CERC), Прага, Ноябрь 29 - Декабрь 1, Задача I