За решение этой задачи вы получите 3 балла.

Манао пытается создать генетический код для новой разновидности водорослей, чтобы эффективно производить горючее. Более конкретно, Манао работает с одной цепочкой ДНК, описывающей некоторый протеин. Цепочка ДНК записывается в виде строки, состоящей из символов 'A', 'T', 'G' и 'C'.

Манао определил, что, если цепочка ДНК содержит максимальную последовательность четной длины из идущих подряд идентичных нуклеотидов, то протеин является нефункциональным. Под максимальной понимается, что до и после этой последовательности нет нуклеотидов того же типа. Например, рассмотрим протеин, записываемый цепочкой ДНК «GTTAAAG». В нем можно выделить четыре максимальные последовательности идующих подряд идентичных нуклеотидов: «G», «TT», «AAA» и «G». Этот протеин нефункционален, так как последовательность «TT» имеет четную длину.

Манао собирается получить из имеющегося у него протеина функциональный протеин. Манао может вставлять в цепочку ДНК протеина дополнительные нуклеотиды — символы из множества {'A', 'T', 'G', 'C'}. Какое минимальное количество вставок потребуется Манао, чтобы протеин, описываемый заданной цепочкой ДНК, стал функциональным?