Binary String

Điểm: 10,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, ~~Kotlin~~, Pascal, PyPy, Python, Scratch

Một xâu nhị phân $S$ . Ta có thể thao tác trên xâu này bằng cách:

Chọn 1 số $p$ bất kì $(1 \leq n)$
Chặt xâu $S$ đang xét ra thành 2 xâu con $S_{x} [1 . . . p]$ , $S_{y} [p + 1 . . . n]$
Lặp lại các thao tác trên các xâu con được tạo ra

Chú ý: $n$ là độ dài của xâu $S$ hiện tại

Một xâu nhị phân được định nghĩa là Hoàn Hảo khi và chỉ khi tất cả các số 0 đến đứng sau số 1

Yêu Cầu: Hãy đếm số lần biến đổi nhỏ nhất để biến đổi xâu $S$ thành một xâu Hoàn Hảo.

INPUT

Gồm một dòng là xâu $S$ $(| S | \leq 10^{7})$

OUTPUT

Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

Subtask 1 (20%): $| S | \leq 100$
Subtask 2 (80%): $| S | \leq 10^{7}$

SAMPLE

Input

Copy

1000111011

Output

Copy

Explanation

Copy

Ta chọn các số x lần lượt là:

x = 7: 1000111|011

x = 4: 1000|111|011

x = 1: 1|000|111|011

-> Sắp xếp lại: 000|011|111|1

-> Thỏa mãn yêu cầu đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

cocomelon đã bình luận 1:55:44 ch, 16/11/2024

ngu qhd mà admin cứ ra qhd là sao @@

-4

abcnickname đã bình luận 1:21:40 sa, 18/11/2024

skibidi

-2

luuquyhiep2010 đã bình luận 4:06:28 ch, 16/11/2024

ke anh

3

cocomelon đã bình luận 1:12:44 sa, 17/11/2024

ừ e