Farmer John có \(N\) con bò đứng thành một hàng (\(1\leq N\leq 3\cdot 10^5\)). Không may, một căn bệnh đang lây lan trong đàn.

Ban đầu, một số con bò bị nhiễm bệnh. Mỗi đêm, một con bò nhiễm bệnh lây bệnh sang con bò bên trái và bên phải nó (nếu có). Một khi đã nhiễm bệnh, con bò sẽ luôn nhiễm bệnh.

Sau một số đêm, Farmer John nhận ra tình hình đã mất kiểm soát nên ông xét nghiệm đàn bò để xác định những con mắc bệnh. Hãy tìm số lượng nhỏ nhất các con bò có thể đã mắc bệnh từ đầu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số bò của Farmer John.

Dòng tiếp theo chứa một xâu bit dài \(N\) chỉ gồm các ký tự \(1\) và \(0\), trong đó \(1\) biểu thị một con bò nhiễm bệnh và \(0\) biểu thị một con bò không nhiễm bệnh sau một số đêm.

Dữ liệu ra

In một số nguyên duy nhất: số lượng nhỏ nhất các con bò có thể đã mắc bệnh từ đầu.

Ví dụ

5
11111

1

0 đêm:       00100 (bò thứ ba bị nhiễm bệnh từ đầu)
1 đêm:    -> 01110 (bò thứ hai và thứ tư vừa bị nhiễm bệnh)
2 đêm:    -> 11111 (bò thứ nhất và thứ năm vừa bị nhiễm bệnh)
3 đêm:    -> 11111 (tất cả bò đã nhiễm bệnh, nên không có thêm bò nào bị nhiễm)
          -> ...

0 đêm:       10001
1 đêm:    -> 11011
2 đêm:    -> 11111

0 đêm:       01001
1 đêm:    -> 11111

0 đêm:       01000
1 đêm:    -> 11100
2 đêm:    -> 11110
3 đêm:    -> 11111

6
011101

4

Phân nhóm

• Dữ liệu 3–7: \(N\le 1000\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Cowntact Tracing 2: https://usaco.org/index.php?page=viewproblem2&cpid=1348

Tác giả bài toán: Suhas Nagar