Preparando MOJI

Balanced String

2000ms 262144K

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.

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.

Sample Input:

101

Sample Output:

0

Sample Input:

1000110

Sample Output:

0

Sample Input:

11010

Sample Output:

1

Sample Input:

11001100

Sample Output:

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$$$.

Informação

Codeforces

Provedor Codeforces

Código CF1860D

Tags

dp

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:41:32

Relacionados

Nada ainda