Codeforces Round 553 (Div. 2) |
---|
Закончено |
Сегодня в научном лицее Королевства Кремляндия был урок биологии. Темой урока были геномы. Назовем геномом строку «ACTG».
Максиму было очень скучно сидеть на уроке, поэтому учитель придумал для него задание: по заданной строке $$$s$$$, состоящей из заглавных латинских букв и длины как минимум $$$4$$$, необходимо найти минимальное количество операций которое нужно применить, чтобы в ней появился геном как подстрока. За одну операцию можно заменить любую букву в строке $$$s$$$ на следующую или предыдущую в алфавите. Например, для буквы «D» предыдущей будет «C», а следующей — «E». В этой задаче считаем, что для буквы «A» предыдущей будет буква «Z», а следующей — буква «B», а для буквы «Z» предыдущей будет буква «Y», а следующей — буква «A».
Помогите Максиму решить задачу, которую дал ему учитель.
Напомним, что строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Первая строка содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 50$$$) — длина строки $$$s$$$.
Вторая строка содержит строку $$$s$$$, состоящую ровно из $$$n$$$ заглавных букв латинского алфавита.
Выведите минимальное количество операций, которые нужно применить к строке $$$s$$$, чтобы в ней появился геном как подстрока.
4 ZCTH
2
5 ZDATG
5
6 AFBAKC
16
В первом примере следует заменить букву «Z» на «A» за одну операцию, букву «H» — на букву «G» за одну операцию. Получится строка «ACTG», в которой присутствует геном как подстрока.
Во втором примере заменим букву «A» на «C» за две операции, букву «D» — на букву «A» за три операции. Получится строка «ZACTG», в которой есть геном.
Название |
---|