← 返回题目列表

Codeforces · 391/A

A. 基因工程

中文机器翻译题面 查看原题

解决此问题将获得 3 分。

Manao 正在设计一种新型藻类的遗传密码,以有效生产燃料。具体来说,Manao 专注于编码一种蛋白质的一段 DNA。 DNA 片段由仅包含字符“A”、“T”、“G”和“C”的字符串表示。

Manao 已经确定,如果 DNA 片段包含长度均匀的连续相同核苷酸的最大序列,则该蛋白质将失去功能。例如,考虑由 DNA 字符串“GTAAAG”描述的蛋白质。它包含四个最大的连续相同核苷酸序列:“G”、“TT”、“AAA”和“G”。该蛋白质没有功能,因为序列“TT”的长度是偶数。

Manao正在尝试从他目前拥有的蛋白质中获取功能性蛋白质。 Manao 可以将额外的核苷酸插入 DNA 片段中。每个额外的核苷酸都是来自集合{'A','T','G','C'}的字符。 Manao 希望确定 DNA 编码功能性蛋白质所需的最少插入次数。

输入

输入由一行组成,其中包含长度为 n (1 ≤ n ≤ 100) 的字符串 s。 s 的每个字符都来自集合 {'A', 'T', 'G', 'C'}。

这个问题没有子问题。正确提交将获得 3 分。

输出

程序应在一行上打印一个整数,表示需要插入到输入字符串中的“A”、“T”、“G”、“C”字符的最小数量,以使所有相同字符的长度都为奇数。

示例

输入 #1

GTTAAAG

输出 #1

1

输入 #2

AACCAACCAAAAC

输出 #2

5

注意

在第一个示例中,在序列中的两个“T”之间插入任何类型的单个核苷酸就足以恢复蛋白质的功能。