CF391A Genetic Engineering

你将通过解决此题获得 3 分。 Manao 正在为一种新型藻类设计遗传密码，以高效生产燃料。具体来说，Manao 正在关注一段编码某种蛋白质的 DNA 区段。该 DNA 区段用只包含字符 ‘A’、‘T’、‘G’ 和 ‘C’ 的字符串表示。 Manao 已经确定，如果 DNA 区段中存在最长的一段连续相同的核苷酸序列且其长度为偶数，则该蛋白质是无功能的。例如，对于 DNA 字符串 "GTTAAAG" 的蛋白质，其包含四段最大长度的连续相同核苷酸序列：“G”、“TT”、“AAA” 和 “G”。该蛋白质是无功能的，因为序列 “TT” 长度为偶数。 Manao 正试图通过插入额外的核苷酸，将当前蛋白质的 DNA 区段变为有功能的蛋白质。每个额外的核苷酸可以是字符集 {'A', 'T', 'G', 'C'} 中的任意一个。Manao 想要知道，最少需要插入多少个核苷酸，才能使得所有由连续相同字符组成的序列长度都为奇数，从而使 DNA 编码的蛋白质有功能。

输入仅一行，包含一个长度为 $n$ 的字符串 $s$（$1 \leq n \leq 100$）。$s$ 中每个字符都是 {'A', 'T', 'G', 'C'} 集合中的一个。 该题没有子任务。提交正确答案可获得 3 分。

程序应输出一行，包含一个整数，表示至少需要插入多少个 'A'、'T'、'G' 或 'C' 字符到输入字符串中，才能使得所有连续相同字符形成的序列长度均为奇数。

在第一个示例中，只需在两个 'T' 之间插入任意一个核苷酸即可使蛋白质恢复功能。 由 ChatGPT 5 翻译