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 @@
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
ừ e