Đi về nhà

Points: 2.5

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Ế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 $O x$ . Ế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 \leq n \leq 100, 1 \leq d \leq 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

Copy

8 4
10010101

Sample Output 1

Copy

Giả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

Copy

4 2
1001

Sample Output 2

Copy

-1

Example 3

Sample Input 3

Copy

12 3
101111100101

Sample Output 3

Copy

Comments

4

TICHPX commented on April 24, 2024, 2:34 p.m.

Chắc phải làm bài lại là $n \leq 10^{6}$ còn $d \leq n$

0

TICHPX commented on April 24, 2024, 2:16 p.m.

Greedy or Breadth First Search or Dynamic Programming