Balanced String
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
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.
Input
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.
Output
Print a single integer — the minimum number of swap operations to make the string $s$ balanced.
101
1000110
11010
11001100
0
0
1
2
Note
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$.
军训训练赛4
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2023-8-24 8:00
- End at
- 2023-8-24 12:00
- Duration
- 4 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 14