Sửa hàng rào


Submit solution

Points: 1 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Thời tiết điên cuồng này là kết quả của sự can thiệp liên tục của nhân loại vào môi trường? Hay đơn giản là chu kỳ thay đổi khí hậu thông qua các thời kỳ? Không ai chắc chắn biết được, nhưng thực tế là các hiện tượng tự nhiên như bão lốc và bão đã đổ vào nước chúng ta mạnh hơn và với tần suất dày đặc hơn hơn nhiều thập kỷ qua.

Một cơn lốc xoáy vừa tấn công trang trại của Mr. Bờm, một nhà sản xuất gia súc và sữa số 1 Việt nam. Nhà bị tốc mái, cây bị nhổ, xe tải bị lật đổ ... Nhưng điều tồi tệ nhất là cơn lốc xoáy phá hủy vài phần của hàng rào bao quanh khu đất. Hàng rào được xây dựng rất tốt, với các cột bê tông cách nhau hai mét, và dây thép gai bao quanh chu vi trại (chu vi, tính bằng mét, là một số nguyên).

Bây giờ một số cột bị hỏng hoặc bị thiếu, và có những khoảng trống trong hàng rào. Để ngăn chặn gia súc thoát khỏi tài sản, hàng rào phải được phục hồi càng nhanh càng tốt. Khôi phục hàng rào với các cột bê tông như cũ sẽ mất một thời gian dài. Vì thế, Mr Bờm đã quyết định sửa tạm bằng gỗ. Tuy nhiên, để làm cho việc xây dựng lại tạm thời nhanh hơn và rẻ hơn, một cột bằng gỗ sẽ cắm thưa hơn: chỉ khi chiều dài của dây rào cần thiết để đóng khoảng cách đến cột tiếp theo (gỗ hoặc bê tông) vượt quá bốn mét.

enter image description here

Đầu vào

Đầu vào chứa một số trường hợp thử nghiệm. Dòng đầu tiên của một trường hợp thử nghiệm chứa một số nguyên N chỉ ra số lượng cột bê tông ban đầu trong hàng rào (5 ≤ N ≤ 5000). Dòng thứ hai của mỗi thử nghiệm chứa N số nguyên X i cho biết trạng thái của mỗi bài bê tông sau cơn lốc xoáy (0 ≤ X i ≤ 1 cho 1 ≤ i ≤ N ). Nếu X i = 1 cột i đang ở trong tình trạng tốt, nếu X i = 0 cột i bị hỏng hoặc mất. Lưu ý rằng cột N sẽ ở cạnh cột .

Kết thúc đầu vào được chỉ ra bởi N = 0.

Đầu ra

Đối với mỗi trường hợp thử nghiệm trong đầu vào, chương trình của bạn phải tạo ra một dòng , chứa một số nguyên cho thấy số lượng cột gỗ nhỏ nhất cần thiết để khôi phục hàng rào, theo quyết định của chủ trại.

VÍ DỤ

INPUT

10

1 0 0 1 0 0 1 0 1 1

11

1 0 0 1 0 0 0 1 1 0 1

12

0 0 0 0 0 1 1 0 0 0 1 1

0

OUTPUT

2

2

3


Comments

There are no comments at the moment.