P10160 [DTCPC 2024] Ultra

Tony2 likes playing a certain two-character game. One day, he showed his $\text{Ultra}$ in front of Xiao C. But Xiao C does not know how to $\text{Ultra}$, so he went to Tutu-jiang. ~~Then Tutu failed~~ So while Tony2 was not around, Xiao C secretly swapped his jump key and down-dash key. (

Tony2’s actions can be seen as a combination of down-dash and jump. An $\text{Ultra}$ is defined as a continuous segment of actions: it starts with a down-dash, then jump and down-dash alternate, and it ends with a down-dash. Since it is an $\text{Ultra}$, it must contain at least one jump. Each time, Xiao C can turn an $\text{Ultra}$ into $\text{uLTRA}$, that is, within this $\text{Ultra}$, change every down-dash into a jump, and change every jump into a down-dash. Xiao C does not like $\text{Ultra}$, so he wants the number of down-dashes to be as small as possible. **Formal statement** You are given a $01$ sequence. You may perform the following operation any number of times (possibly zero times): - Replace a substring of the form $101\cdots01$ (i.e., $1(01)^k$, $k\ge 1$) with an **equal-length** substring $010\cdots10$ (i.e., $0(10)^k$). Your goal is to make the number of $1$’s as small as possible. Output the minimum possible number of $1$’s.

One line contains a string of length $n$ ($n\le 10^6$) representing this $01$ sequence.

Output one number, the minimum possible number of $1$’s.

Explanation for sample $1$: choose the first three characters $101$. After applying the operation, the string becomes $0100011$, which contains only $3$ ones. It is easy to prove that this is optimal. Translated by ChatGPT 5