CF1860D.Balanced String

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given a binary string $s$ (a binary string is a string consisting of characters 0 and/or 1).

Let's call a binary string balanced if the number of subsequences 01 (the number of indices $i$ and $j$ such that $1 \le i < j \le n$ , $s_i=0$ and $s_j=1$ ) equals to the number of subsequences 10 (the number of indices $k$ and $l$ such that $1 \le k < l \le n$ , $s_k=1$ and $s_l=0$ ) in it.

For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $6$ . On the other hand, 11010 is not balanced, because the number of subsequences 01 is $1$ , but the number of subsequences 10 is $5$ .

You can perform the following operation any number of times: choose two characters in $s$ and swap them. Your task is to calculate the minimum number of operations to make the string $s$ balanced.

输入格式

The only line contains the string $s$ ( $3 \le |s| \le 100$ ) consisting of characters 0 and/or 1.

Additional constraint on the input: the string $s$ can be made balanced.

输出格式

Print a single integer — the minimum number of swap operations to make the string $s$ balanced.

输入输出样例

输入#1
```
101
```
输出#1
```
0
```
输入#2
```
1000110
```
输出#2
```
0
```
输入#3
```
11010
```
输出#3
```
1
```
输入#4
```
11001100
```
输出#4
```
2
```

说明/提示

In the first example, the string is already balanced, the number of both 01 and 10 is equal to $1$ .

In the second example, the string is already balanced, the number of both 01 and 10 is equal to $6$ .

In the third example, one of the possible answers is the following one: 11010 $\rightarrow$ 01110. After that, the number of both 01 and 10 is equal to $3$ .

In the fourth example, one of the possible answers is the following one: 11001100 $\rightarrow$ 11001010 $\rightarrow$ 11000011. After that, the number of both 01 and 10 is equal to $8$ .

首页