CF391A.Genetic Engineering

You will receive 3 points for solving this problem.

Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.

解决本题可获得 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 编码功能性蛋白质所需的最少插入次数。

The input consists of a single line, containing a string s of length n (1 ≤ n ≤ 100). Each character of s will be from the set {'A', 'T', 'G', 'C'}.

This problem doesn't have subproblems. You will get 3 points for the correct submission.

输入仅包含一行，该行包含一个长度为 $n$（$1 ≤ n ≤ 100$）的字符串 $s$。字符串 $s$ 中的每个字符均来自集合 $\{'A', 'T', 'G', 'C'\}$。

本题没有子问题。正确提交可获得 3 分。

The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.

程序应在一行中输出一个整数，表示为使输入字符串中所有相同字符的连续段（run）长度均为奇数，所需插入的字符 'A'、'T'、'G'、'C' 的最小个数。

In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.

在第一个例子中，只需在序列中两个“T”之间插入任意一种核苷酸，即可恢复蛋白质的功能。