Description

給定一個長度為 $N$ 的 0/1 字串,並定義一次操作為進行下列兩種操作之一:

  1. 修改任意一個字元的值
  2. 把任意前綴全部取反(0 變 1、1 變 0)

請問最少需要多少次操作才能把這個字串改變為全部為 1 的字串呢?

Input Format

輸入只有一行包含一個 0/1 字串。

對於所有測資,$N\leq 1.5\times 10^ 9$。
對於 100 分的測資,$N\leq 5\times 10^ 7$。

Output Format

請輸出一行包含一個非負整數,代表最少需要的操作次數。

對於所有測資,若你的程式執行時間為時限的 $x$ 倍($0\leq x\leq 1$),該筆測資的分數為 $A\times (p+qf(x))$,其中 $A$ 為該筆測資標示的分數、$p,q$ 為各測資敘述上標示的常數,並給定常數 $a=1.5,b=0.15$,

\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]

\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]

你只需要知道 $f(0)=1,f(1)=0$,且 $f(x)$ 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話,可以參考這個連結

Sample Input 1

100011011

Sample Output 1

3

Hints

Problem Source

TIOJ 1853 / TIOJ 終極壓常數大賽 pA

Subtasks

No. Testdata Range Constraints Score
1 0 $p=1,q=0.2$ 50
2 1 $p=1,q=0.2$ 50
3 2 $p=0,q=1$ 25
4 3 $p=0,q=1$ 120
5 4 $p=0,q=1$ 75
6 5 $p=0,q=1$ 75
7 6 $p=0,q=1$ 90
8 7 $p=q=0.5$ 40
9 8 $p=q=0.5$ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1100 262144 4 1
1 1100 262144 4 2
2 1100 65536 4 3
3 1100 65536 4 4
4 1100 65536 4 5
5 1100 65536 4 6
6 1100 65536 4 7
7 650 65536 4 8
8 650 65536 4 9