Xâu đẹp
Đề bài
Mô tả
Xâu nhị phân là xâu chỉ gồm các ký tự 0 và 1. Một xâu nhị phân được gọi là đẹp nếu với mỗi ký tự 1 trong xâu, số ký tự 0 liên tiếp tính từ nó sang trái đến ký tự 1 gần nhất (hoặc đến đầu xâu) bằng số ký tự 0 liên tiếp tính từ nó sang phải đến ký tự 1 gần nhất (hoặc đến cuối xâu). Nói cách khác, với mỗi ký tự 1, số ký tự 0 liên tiếp ngay bên trái nó bằng số ký tự 0 liên tiếp ngay bên phải nó. Ví dụ, xâu 0001000 là xâu đẹp, còn xâu 001010 không đẹp vì bên trái ký tự 1 đầu tiên có hai ký tự 0, còn bên phải nó chỉ có một ký tự 0.
Cho một xâu nhị phân, bạn cần xóa một số ký tự của nó để được một xâu đẹp. Hãy in ra độ dài lớn nhất của xâu đẹp có thể nhận được bằng cách xóa các ký tự của xâu đã cho. Xâu kết quả phải chứa ít nhất một ký tự 1.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : độ dài xâu nhị phân ().
- Dòng thứ hai chứa xâu gồm ký tự, mỗi ký tự là 0 hoặc 1. Dữ liệu đảm bảo xâu chứa ít nhất một ký tự 1.
Dữ liệu ra
In ra một số nguyên là độ dài lớn nhất của xâu đẹp nhận được.
Ràng buộc
- Xâu chỉ gồm các ký tự 0 và 1, có ít nhất một ký tự 1.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 0000010100 |
7 | Xóa ký tự 1 cuối cùng và hai ký tự 0 đầu tiên để được xâu 0001000. |
| 4 1111 |
4 | Xâu 1111 đã là xâu đẹp, không cần xóa ký tự nào. |
| 7 0101001 |
5 | Xóa hai ký tự cuối để được xâu đẹp 01010. |
Bình luận