{"problem":{"name":"A. The Way to Home","description":{"content":"A frog lives on the axis _Ox_ and needs to reach home which is in the point _n_. She starts from the point 1. The frog can jump to the right at a distance not more than _d_. So, after she jumped from ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF910A"},"statements":[{"statement_type":"Markdown","content":"A frog lives on the axis _Ox_ and needs to reach home which is in the point _n_. She starts from the point 1. The frog can jump to the right at a distance not more than _d_. So, after she jumped from the point _x_ she can reach the point _x_ + _a_, where _a_ is an integer from 1 to _d_.\n\nFor each point from 1 to _n_ is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and _n_.\n\nDetermine the minimal number of jumps that the frog needs to reach home which is in the point _n_ from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print _\\-1_.\n\n## Input\n\nThe first line contains two integers _n_ and _d_ (2 ≤ _n_ ≤ 100, 1 ≤ _d_ ≤ _n_ - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.\n\nThe second line contains a string _s_ of length _n_, consisting of zeros and ones. If a character of the string _s_ equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string _s_ equal to one.\n\n## Output\n\nIf the frog can not reach the home, print _\\-1_.\n\nIn the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point _n_ from the point 1.\n\n[samples]\n\n## Note\n\nIn the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).\n\nIn the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一只青蛙生活在数轴 #cf_span[Ox] 上，需要到达位于点 #cf_span[n] 的家。它从点 #cf_span[1] 出发。青蛙每次可以向右跳跃不超过 #cf_span[d] 的距离。因此，当它从点 #cf_span[x] 跳跃后，可以到达点 #cf_span[x + a]，其中 #cf_span[a] 是一个介于 #cf_span[1] 到 #cf_span[d] 之间的整数。\n\n对于从 #cf_span[1] 到 #cf_span[n] 的每个点，已知该点是否有睡莲。青蛙只能落在有睡莲的点上。保证点 #cf_span[1] 和点 #cf_span[n] 上都有睡莲。\n\n求青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。假设青蛙初始位于点 #cf_span[1]。如果青蛙无法到达家，请输出 _-1_。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[2 ≤ n ≤ 100]，#cf_span[1 ≤ d ≤ n - 1]）——分别表示青蛙想要到达的点和青蛙跳跃的最大长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由 0 和 1 组成。如果字符串 #cf_span[s] 的某个字符为 0，则对应点没有睡莲；否则，该点有睡莲。保证字符串 #cf_span[s] 的第一个和最后一个字符均为 1。\n\n## Output\n\n如果青蛙无法到达家，请输出 _-1_。否则，输出青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。\n\n[samples]\n\n## Note\n\n在第一个例子中，青蛙可以通过两次跳跃到达家：第一次从点 #cf_span[1] 跳到点 #cf_span[4]（跳跃长度为三），第二次从点 #cf_span[4] 跳到点 #cf_span[8]（跳跃长度为四）。在第二个例子中，青蛙无法到达家，因为要到达家需要跳跃距离为三，但其最大跳跃长度仅为二。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, d \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 100 $, $ 1 \\leq d \\leq n-1 $.  \nLet $ s \\in \\{0,1\\}^n $ be a binary string where $ s[i] = 1 $ iff a lily flower is present at position $ i+1 $ (1-indexed).  \nGiven: $ s[0] = 1 $ and $ s[n-1] = 1 $.\n\nLet $ V = \\{ i \\in \\{1, \\dots, n\\} \\mid s[i-1] = 1 \\} $ be the set of positions with lilies.\n\n**Constraints**  \nThe frog starts at position $ 1 $ and must reach position $ n $.  \nFrom any position $ x \\in V $, the frog may jump to position $ y \\in V $ iff $ 1 \\leq y - x \\leq d $.\n\n**Objective**  \nFind the minimum number of jumps to reach $ n $ from $ 1 $, using only positions in $ V $.  \nIf no such path exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF910A","tags":["dfs and similar","dp","greedy","implementation"],"sample_group":[["8 4\n10010101","2"],["4 2\n1001","\\-1"],["8 4\n11100101","3"],["12 3\n101111100101","4"]],"created_at":"2026-03-03 11:00:39"}}