Binary String
Xem dạng PDF
Gửi bài giải
Đ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 \le 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| \le 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| \le 100~
- Subtask 2 (80%): ~|S| \le 10^7~
SAMPLE
Input
1000111011
Output
3
Explanation
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
ngu qhd mà admin cứ ra qhd là sao @@
skibidi
ke anh
ừ e