A. Ostap and Grasshopper

Codeforces
IDCF735A
Time2000ms
Memory256MB
Difficulty
implementationstrings
English · Original
Chinese · Translation
Formal · Original
On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length _n_ such that some cells of this line are empty and some contain obstacles. Then, he places his grasshopper to one of the empty cells and a small insect in another empty cell. The grasshopper wants to eat the insect. Ostap knows that grasshopper is able to jump to any empty cell that is **exactly** _k_ cells away from the current (to the left or to the right). Note that it doesn't matter whether intermediate cells are empty or not as the grasshopper makes a jump over them. For example, if _k_ = 1 the grasshopper can jump to a neighboring cell only, and if _k_ = 2 the grasshopper can jump over a single cell. Your goal is to determine whether there is a sequence of jumps such that grasshopper will get from his initial position to the cell with an insect. ## Input The first line of the input contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ _n_ - 1) — the number of cells in the line and the length of one grasshopper's jump. The second line contains a string of length _n_ consisting of characters '_._', '_#_', '_G_' and '_T_'. Character '_._' means that the corresponding cell is empty, character '_#_' means that the corresponding cell contains an obstacle and grasshopper can't jump there. Character '_G_' means that the grasshopper starts at this position and, finally, '_T_' means that the target insect is located at this cell. It's guaranteed that characters '_G_' and '_T_' appear in this line **exactly once**. ## Output If there exists a sequence of jumps (each jump of length _k_), such that the grasshopper can get from his initial position to the cell with the insect, print "_YES_" (without quotes) in the only line of the input. Otherwise, print "_NO_" (without quotes). [samples] ## Note In the first sample, the grasshopper can make one jump to the right in order to get from cell 2 to cell 4. In the second sample, the grasshopper is only able to jump to neighboring cells but the way to the insect is free — he can get there by jumping left 5 times. In the third sample, the grasshopper can't make a single jump. In the fourth sample, the grasshopper can only jump to the cells with odd indices, thus he won't be able to reach the insect.
在前往里约热内卢的路上,Ostap 用他放在特制盒子中的蚱蜢打发时间。Ostap 构建了一条长度为 $n$ 的直线,其中一些格子为空,另一些包含障碍物。然后,他将蚱蜢放在其中一个空格子上,并将一只小昆虫放在另一个空格子上。蚱蜢想要吃掉昆虫。 Ostap 知道蚱蜢能够跳到距离当前位置 *恰好* $k$ 个格子的任意空格子上(向左或向右)。注意,中间格子是否为空无关紧要,因为蚱蜢会跳过它们。例如,如果 $k = 1$,蚱蜢只能跳到相邻的格子;如果 $k = 2$,蚱蜢可以跳过一个格子。 你的目标是判断是否存在一系列跳跃,使得蚱蜢能从初始位置到达昆虫所在的格子。 输入的第一行包含两个整数 $n$ 和 $k$($2 ≤ n ≤ 100$,$1 ≤ k ≤ n - 1$)—— 表示直线上的格子数和蚱蜢一次跳跃的长度。 第二行是一个长度为 $n$ 的字符串,由字符 '_.'、'_#_'、'_G_' 和 '_T_' 组成。字符 '_.' 表示对应格子为空,字符 '_#_' 表示对应格子包含障碍物,蚱蜢不能跳到那里。字符 '_G_' 表示蚱蜢的起始位置,字符 '_T_' 表示目标昆虫所在的位置。保证字符 '_G_' 和 '_T_' 在该字符串中各出现 *恰好一次*。 如果存在一系列跳跃(每次跳跃长度为 $k$),使得蚱蜢能从初始位置到达昆虫所在格子,则在输入的唯一一行中输出 "_YES_"(不含引号);否则输出 "_NO_"(不含引号)。 在第一个样例中,蚱蜢可以向右跳一次,从第 $2$ 个格子跳到第 $4$ 个格子。 在第二个样例中,蚱蜢只能跳到相邻格子,但通往昆虫的路径是畅通的——它可以通过向左跳 $5$ 次到达。 在第三个样例中,蚱蜢无法做出任何跳跃。 在第四个样例中,蚱蜢只能跳到奇数编号的格子,因此无法到达昆虫。 ## Input 输入的第一行包含两个整数 $n$ 和 $k$($2 ≤ n ≤ 100$,$1 ≤ k ≤ n - 1$)—— 表示直线上的格子数和蚱蜢一次跳跃的长度。第二行是一个长度为 $n$ 的字符串,由字符 '_.'、'_#_'、'_G_' 和 '_T_' 组成。字符 '_.' 表示对应格子为空,字符 '_#_' 表示对应格子包含障碍物,蚱蜢不能跳到那里。字符 '_G_' 表示蚱蜢的起始位置,字符 '_T_' 表示目标昆虫所在的位置。保证字符 '_G_' 和 '_T_' 在该字符串中各出现 *恰好一次*。 ## Output 如果存在一系列跳跃(每次跳跃长度为 $k$),使得蚱蜢能从初始位置到达昆虫所在格子,则在输入的唯一一行中输出 "_YES_"(不含引号);否则输出 "_NO_"(不含引号)。 [samples] ## Note 在第一个样例中,蚱蜢可以向右跳一次,从第 $2$ 个格子跳到第 $4$ 个格子。在第二个样例中,蚱蜢只能跳到相邻格子,但通往昆虫的路径是畅通的——它可以通过向左跳 $5$ 次到达。在第三个样例中,蚱蜢无法做出任何跳跃。在第四个样例中,蚱蜢只能跳到奇数编号的格子,因此无法到达昆虫。
**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 100 $, $ 1 \leq k \leq n-1 $. Let $ s \in \{ \texttt{.}, \texttt{\#}, \texttt{G}, \texttt{T} \}^n $ be a string representing the line of cells. Let $ g, t \in \{0, 1, \dots, n-1\} $ be the unique indices such that $ s[g] = \texttt{G} $ and $ s[t] = \texttt{T} $. **Constraints** 1. For all $ i \in \{0, \dots, n-1\} $, if $ s[i] = \texttt{\#} $, then cell $ i $ is blocked. 2. $ s[g] = \texttt{G} $, $ s[t] = \texttt{T} $, and both $ s[g] \neq \texttt{\#} $, $ s[t] \neq \texttt{\#} $. **Objective** Determine whether there exists a finite sequence of positions $ p_0, p_1, \dots, p_m $ such that: - $ p_0 = g $, - $ p_m = t $, - For each $ j \in \{1, \dots, m\} $, $ |p_j - p_{j-1}| = k $, - For all $ j \in \{0, \dots, m\} $, $ s[p_j] \neq \texttt{\#} $. Output "YES" if such a sequence exists; otherwise, output "NO".
Samples
Input #1
5 2
#G#T#
Output #1
YES
Input #2
6 1
T....G
Output #2
YES
Input #3
7 3
T..#..G
Output #3
NO
Input #4
6 2
..GT..
Output #4
NO
API Response (JSON)
{
  "problem": {
    "name": "A. Ostap and Grasshopper",
    "description": {
      "content": "On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length _n_ such that some cells of this line are empty and some conta",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF735A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On the way to Rio de Janeiro Ostap kills time playing with a grasshopper he took with him in a special box. Ostap builds a line of length _n_ such that some cells of this line are empty and some conta...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在前往里约热内卢的路上,Ostap 用他放在特制盒子中的蚱蜢打发时间。Ostap 构建了一条长度为 $n$ 的直线,其中一些格子为空,另一些包含障碍物。然后,他将蚱蜢放在其中一个空格子上,并将一只小昆虫放在另一个空格子上。蚱蜢想要吃掉昆虫。\n\nOstap 知道蚱蜢能够跳到距离当前位置 *恰好* $k$ 个格子的任意空格子上(向左或向右)。注意,中间格子是否为空无关紧要,因为蚱蜢会跳过它们。例如,如...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 100 $, $ 1 \\leq k \\leq n-1 $.  \nLet $ s \\in \\{ \\texttt{.}, \\texttt{\\#}, \\texttt{G}, \\texttt{T} \\}^n $ be a string representing the li...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments