COCI 2016/2017 - Contest 6 - Telefoni
Xem dạng PDF
Trong một căn phòng, có ~N~ cái bàn được xếp thành một hàng ngang, lần lượt từ trái sang phải. Một số bàn có điện thoại, và một số thì không. Tất cả các điện thoại đều gặp vấn đề nên điện thoại trên bàn ~i~ sẽ đổ chuông khi điện thoại trên bàn ~j~ đổ chuông, nếu bàn ~j~ cách bàn ~i~ không quá ~D~ bàn ~(|i-j| \le D)~. Bàn đầu tiên và bàn cuối cùng luôn có điện thoại. Ban đầu, điện thoại trên bàn ngoài cùng bên trái sẽ đổ chuông. Phải đặt thêm ít nhất bao nhiêu chiếc điện thoại lên các bàn khác để điện thoại trên bàn cuối cùng cũng đổ chuông?
Input
Dòng đầu tiên gồm ~2~ số nguyên dương, ~N~ ~(1 \le N \le 300\:000)~ và ~D~ ~(1 \le D \le N)~.
Dòng tiếp theo gồm ~N~ số ~0~ hoặc ~1~. Nếu số thứ ~i~ là ~1~ thì có điện thoại ở trên bàn thứ ~i~, và nếu số thứ ~i~ là ~0~ thì ngược lại.
Output
Số nguyên duy nhất là số điện thoại tối thiểu cần đặt thêm.
Sample 1
Input
4 1
1 0 1 1
Output
1
Sample 2
Input
5 2
1 0 0 0 1
Output
1
Sample 3
Input
8 2
1 1 0 0 1 0 0 1
Output
2
Subtask
- ~5~ test đầu tiên có ~N \le 20~.
- ~5~ test còn lại không có điều kiện gì thêm.
Bình luận
Mai son:
Ý tưởng tham lam:
Xét cả 3 ví dụ ta thấy cả 3 đều được đặt điện thoại ở các vị trí không có điện thoại(vị trí số '0')
Vậy chỉ cần tìm 'các' khoảng cách liên tục của các số '0' tức là khoảng cách không có điện thoại
Xong lấy từng các khoảng cách ấy '/' cho 'D' và cộng dồn vào
Ae thấy hay cho tui xin up vote nhé🙏