Решение задачи Максим и биология с Codeforces

Без пояснения   Просмотров: 19


Сегодня в научном лицее Королевства Кремляндия был урок биологии. Темой урока были геномы. Назовем геномом строку «ACTG».

Максиму было очень скучно сидеть на уроке, поэтому учитель придумал для него задание: по заданной строке s, состоящей из заглавных латинских букв и длины как минимум 4, необходимо найти минимальное количество операций которое нужно применить, чтобы в ней появился геном как подстрока. За одну операцию можно заменить любую букву в строке s на следующую или предыдущую в алфавите. Например, для буквы «D» предыдущей будет «C», а следующей — «E». В этой задаче считаем, что для буквы «A» предыдущей будет буква «Z», а следующей — буква «B», а для буквы «Z» предыдущей будет буква «Y», а следующей — буква «A».

Помогите Максиму решить задачу, которую дал ему учитель.

Напомним, что строка a является подстрокой b, если a может быть получена из b удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Код

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n,sum,ans=INT_MAX,i,j,num;
	string s,x="ACTG";
	cin >> n >> s;
	
	for(i=0;i<n-3;++i)
	{
		sum=0;
		for(j=0;j<4;++j)
		{
			num=abs(s[i+j]-x[j]);
			if(num>13) num = 26-num;
			sum+=num;
		}
		ans = min(sum,ans);
	}
	cout << ans;
	
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться