P2708 Coin Flipping

There are many coins placed in a row. Heads-up is represented by $1$, and tails-up is represented by $0$. Starting from the first coin in the row, in each operation you must flip the first several coins simultaneously, i.e., choose some $k \ge 1$ and flip the first $k$ coins. What is the minimum number of such operations needed to make all coins heads-up?

A string consisting of $0$ and $1$, representing the initial state of the coins.

An integer, the minimum number of flips required.

### Sample Explanation For example, for input 10: - The $1$-st flip: flip the first coin to tails; the string becomes 00. - The $2$-nd flip: flip the first and second coins together to heads; the string becomes 11. Flipping is complete, so the output is $2$. ### Constraints Let $n$ be the total number of coins. - For $20\%$ of the testdata, $1\le n\leq10$. - For $50\%$ of the testdata, $1\le n\leq10^4$. - For $100\%$ of the testdata, $1\le n\leq10^6$. Translated by ChatGPT 5