A. The Way to Home

Codeforces

IDCF910A

Time1000ms

Memory256MB

Difficulty—

dfs and similardpgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

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_. For 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_. Determine 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_. ## Input The 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. The 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. ## Output If the frog can not reach the home, print _\-1_. In 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. [samples] ## Note In 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). In 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.

一只青蛙生活在数轴 #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] 之间的整数。对于从 #cf_span[1] 到 #cf_span[n] 的每个点，已知该点是否有睡莲。青蛙只能落在有睡莲的点上。保证点 #cf_span[1] 和点 #cf_span[n] 上都有睡莲。求青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。假设青蛙初始位于点 #cf_span[1]。如果青蛙无法到达家，请输出 _-1_。 ## Input 第一行包含两个整数 #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。 ## Output 如果青蛙无法到达家，请输出 _-1_。否则，输出青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。 [samples] ## Note 在第一个例子中，青蛙可以通过两次跳跃到达家：第一次从点 #cf_span[1] 跳到点 #cf_span[4]（跳跃长度为三），第二次从点 #cf_span[4] 跳到点 #cf_span[8]（跳跃长度为四）。在第二个例子中，青蛙无法到达家，因为要到达家需要跳跃距离为三，但其最大跳跃长度仅为二。

**Definitions** Let $ n, d \in \mathbb{Z} $ with $ 2 \leq n \leq 100 $, $ 1 \leq d \leq n-1 $. Let $ 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). Given: $ s[0] = 1 $ and $ s[n-1] = 1 $. Let $ V = \{ i \in \{1, \dots, n\} \mid s[i-1] = 1 \} $ be the set of positions with lilies. **Constraints** The frog starts at position $ 1 $ and must reach position $ n $. From any position $ x \in V $, the frog may jump to position $ y \in V $ iff $ 1 \leq y - x \leq d $. **Objective** Find the minimum number of jumps to reach $ n $ from $ 1 $, using only positions in $ V $. If no such path exists, output $ -1 $.

Samples

Input #1

8 4
10010101

Output #1

Input #2

4 2
1001

Output #2

\-1

Input #3

8 4
11100101

Output #3

Input #4

12 3
101111100101

Output #4

API Response (JSON)

{
  "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 ...",
      "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对于...",
      "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 positio...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments