← 返回题目列表

Codeforces · 1860/D

D. 平衡弦

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

给定一个二进制字符串 $$$s$$$(二进制字符串是由字符 0 和/或 1 组成的字符串)。

如果子序列 01 的数量(索引 $$$i$$$ 和 $$$j$$$ 的数量,使得 $$$1 \le i < j \le n$$$、$$$s_i=0$$$ 和 $$$s_j=1$$$)等于子序列 10 的数量(索引 $$$k$$$ 的数量),我们称二进制字符串是平衡的和 $$$l$$$ 使得 $$$1 \le k < l \le n$$$, $$$s_k=1$$$ 和 $$$s_l=0$$$) 。

例如,字符串 1000110 是平衡的,因为子序列 01 的数量和子序列 10 的数量都等于 $$$6$$$。另一方面,11010是不平衡的,因为子序列01的数量是$$$1$$$,但是子序列10的数量是$$$5$$$。

您可以多次执行以下操作:在 $$$s$$$ 中选择两个字符并交换它们。你的任务是计算使字符串 $$$s$$$ 平衡所需的最少操作数。

输入

唯一一行包含由字符 0 和/或 1 组成的字符串 $$$s$$$ ($$$3 \le |s| \le 100$$$)。

输入的附加约束:字符串 $$$s$$$ 可以平衡。

输出

打印单个整数 - 使字符串 $$$s$$$ 平衡的交换操作的最小数量。

示例

输入 #1

101

输出 #1

0

输入 #2

1000110

输出 #2

0

输入 #3

11010

输出 #3

1

输入#4

11001100

输出#4

2

注意

在第一个示例中,字符串已经平衡,01 和 10 的数量都等于 $$$1$$$。

在第二个示例中,字符串已经平衡,01 和 10 的数量都等于 $$$6$$$。

在第三个示例中,可能的答案之一如下:11010 $$$\rightarrow$$$ 01110。之后,01 和 10 的数字都等于 $$$3$$$。

在第四个示例中,可能的答案之一如下: 11001100 $$$\rightarrow$$$ 11001010 $$$\rightarrow$$$ 11000011。之后,01 和 10 的数字都等于 $$$8$$$。