Truy Vết Tiếp Xúc 2

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John có $N$ con bò xếp thành một hàng. Một số con bò ban đầu bị nhiễm bệnh. Mỗi đêm, một con bò bị nhiễm bệnh sẽ lây lan bệnh sang con bò liền kề bên trái và bên phải (nếu tồn tại). Một khi con bò đã bị nhiễm, nó sẽ luôn bị nhiễm.

Cho trạng thái cuối cùng của các con bò sau một số đêm, hãy xác định số lượng tối thiểu con bò có thể đã bị nhiễm bệnh ban đầu.

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ ( $1 \leq N \leq 3 \cdot 10^{5}$ ).
Dòng $2$ : Xâu $N$ ký tự gồm các chữ số $0$ và $1$ , trong đó $1$ biểu thị con bò bị nhiễm bệnh và $0$ biểu thị con bò không bị nhiễm.

Dữ liệu ra

In ra một số nguyên duy nhất -- số lượng tối thiểu con bò ban đầu bị nhiễm bệnh.

Ràng buộc

Các test $3$ - $7$ : $N \leq 1000$ .
Các test $8$ - $12$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
5 11111	1	Một con bò ban đầu bị nhiễm ở vị trí giữa, sau 2 đêm lan ra tất cả các con bò.
6 011101	4	Con bò ở vị trí 5 (0-indexed 4) không bị nhiễm, chứng tỏ không có đêm nào trôi qua. Do đó cả 4 con bò bị nhiễm đều phải là ban đầu.

Bình luận

Không có bình luận tại thời điểm này.