Đi về nhà
Ếch con đang ngồi trên một bông hoa sen. Những lá sen và hoa sen xếp thành một hàng theo trục \(Ox\). Ếch đang ngồi ở điểm có tọa độ là \(1\), nhà của ếch ở điểm có tọa độ \(n\). Ếch có thể nhảy sang phải một khoảng cách không quá \(d\). Tức là từ điểm \(x\), ếch có thế nhảy đến điểm \(x + a\) với \(a\) là số nguyên từ \(1\) đến \(d\).
Với mỗi điểm từ \(1\) đến \(n\) có chứa lá sen hoặc hoa sen. Ếch thích hoa nên chỉ nhảy đến những điểm mà tại đó là hoa sen, những điểm mà tại đó là lá sen ếch sẽ không chịu nhảy. Input đảm bảo điểm \(1\) và điểm \(n\) chứa hoa sen.
Xác định số bước ít nhất ếch cần nhảy từ vị trí \(1\) để về đến nhà ở vị trí \(n\). Nếu ếch không nhảy được về nhà, in ra \(-1\).
Input
Dòng đầu tiên chứa 2 số nguyên \(n\) và \(d\) \((2 \le n \le 100, 1 \le d \le n - 1)\) lần lượt là tọa độ nhà của ếch và khoảng cách tối đa mỗi bước nhảy của ếch.
Dòng thứ 2 chứa chuỗi \(s\) có độ dài \(n\) gồm các ký tự \(0\) và \(1\). Nếu một ký tự ở chuỗi \(s\) bằng \(0\) thì ở vị trí tương ứng có chứa lá sen, ngược lại nếu bằng \(1\) thì ở vị trí tương ứng có chứa hoa sen. Input đảm bảo ký tự đầu tiên và ký tự cuối cùng của chuỗi \(s\) bằng \(1\).
Output
Nếu ếch không thể về nhà, in ra \(-1\).
Trong trường hợp có thể về nhà được, in ra số lần nhảy ít nhất mà ếch cần nhảy để về nhà.
Example 1
Sample Input 1
8 4
10010101Sample Output 1
2Giải thích: Ếch nhảy từ điểm \(1\) đến điểm \(4\), sau đó nhảy đến điểm \(8\) là tới nhà. Số bước nhảy ít nhất là \(2\).
Example 2
Sample Input 2
4 2
1001Sample Output 2
-1Example 3
Sample Input 3
12 3
101111100101Sample Output 3
4
Comments
Chắc phải làm bài lại là \(n \leq 10^6\) còn \(d \leq n\)
Greedy or Breadth First Search or Dynamic Programming