← 返回题目列表

Codeforces · 49/D

D. 游戏

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

Vasya 和 Petya 发明了一种新游戏。 Vasya 采用由 1 × n 方格组成的条纹,并将方格涂成黑色和白色。之后,Petya 可以开始移动——在移动过程中,他可以选择任意两个相邻的一种颜色的方块,并以他想要的方式重新绘制这两个方块,也许可以用不同的颜色。 Petya 只能将方块重新绘制为白色和黑色。佩蒂亚的目标是重新绘制条纹,这样相邻的两个方块就不会是同一种颜色。帮助 Petya,使用给定的初始颜色,找到 Petya 获胜所需的最少步数。

输入

第一行包含数字 n (1 ≤ n ≤ 1000),表示条带的长度。第二行恰好包含 n 个符号——该行的初始颜色。 0 对应白色方块,1 对应黑色方块。

输出

如果 Petya 无法通过这样的初始着色获胜,则打印 -1。否则打印 Petya 获胜所需的最小步数。

示例

输入 #1

6
111010

输出 #1

1

输入 #2

5
10001

输出 #2

1

输入 #3

7
1100010

输出 #3

2

输入#4

5
00100

输出#4

2

注意

在第一个示例中,Petya 可以选取方格 1 和 2。他将方格 1 重新绘制为黑色,将方格 2 重新绘制为白色。

在第二个示例中,Petya 可以选取方格 2 和 3。他将方格 2 重新绘制为白色,将方格 3 重新绘制为黑色。