Mô tả
Tại cửa hàng Bách Hóa Xanh, mỗi mặt hàng được dán một mã vạch dạng chuỗi nhị phân độ dài n. Khi quét tại máy tự phục vụ, hệ thống yêu cầu mã vạch phải có tính đối xứng — tức đọc từ trái sang phải giống hệt đọc từ phải sang trái — thì mới chấp nhận thanh toán.
Do lỗi in ấn, một số mã vạch chưa đối xứng. Nhân viên vận hành muốn biết: cần lật tối thiểu bao nhiêu bit (đổi 0 thành 1 hoặc 1 thành 0) để mã vạch trở thành chuỗi đối xứng? Hãy viết chương trình giúp tính số lần lật bit ít nhất.
Đầu vào
- Một chuỗi
sgồm duy nhất các ký tự'0'và'1', độ dàin(1 <= n <= 10^5).
Đầu ra
- In ra một số nguyên duy nhất: số lần lật bit tối thiểu để
strở thành chuỗi đối xứng.
Ràng buộc
1 <= n <= 10^5- Chuỗi chỉ chứa ký tự
'0'hoặc'1'.
Ví dụ
Ví dụ 1:
- Đầu vào:
s = "00110" - Đầu ra:
2
Giải thích: Các cặp đối xứng là (vị trí 0, 4): '0' và '0' — khớp; (vị trí 1, 3): '0' và '1' — khác, cần lật 1 bit; (vị trí 2): '1' — ở giữa, không cần so. Tổng cộng cần lật 2 bit (vì có hai cặp khác nhau). Thực tế chuỗi "00110" có hai vị trí (1,3) khác nhau, lật một trong hai là được, nhưng kết quả chỉ cần đếm số cặp khác nhau.
Chờ đã — ta đếm lại: vị trí 0 vs 4: '0' vs '0' → giống. Vị trí 1 vs 3: '0' vs '1' → khác. Vị trí 2 ở giữa (n lẻ) không ghép. Vậy chỉ có 1 cặp khác nhau. Đáp án đúng là 1. (Đầu ra đúng: 1.)