| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P202PROG - Xâu nhị phân hoàn hảo |
Mincy có một xâu nhị phân (chỉ bao gồm 0 và 1). Mincy muốn có được một xâu nhị phân hoàn hảo nên cô ấy muốn thực hiện biến đổi:
Thay bit 1 thành bit 0 hoặc ngược lại tại 1 vị trí trong xâu.
Hãy giúp Mincy tính số lần thực hiện biến đổi ít nhất để xâu nhị phân trở lên hoàn hảo.
Dãy nhị phân hoàn hảo được Mincy định nghĩa là dãy nhị phân không có xâu con “010” hay “101” nào được tạo thành từ xâu nhị phân. Ví dụ “1001” chứa “101” là xâu con nên không thể là xâu nhị phân hoàn hảo trong khi “1000” thì là dãy nhị phân hoàn hảo.
Input
Dòng đầu tiên chứa T là số lượng test (1 <= T <= 100).
T dòng tiếp theo mỗi dòng chứa một xâu nhị phân S (1 <= length(S) <= 1000).
Output
Đối với mỗi xâu in ra số lượng biến đổi ít nhất để có xâu nhị phân hoàn hảo
Example
|
Input |
Output |
|
7 001 100 101 010 0 1 001100 |
0 0 1 1 0 0 2 |
| Được gửi lên bởi: | adm |
| Ngày: | 2020-08-22 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 5000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM64 CPP CPP14 JAVA PYTHON PYTHON3 |
