← 返回题目列表

Codeforces · 735/A

A. 奥斯塔普和蚱蜢

中文机器翻译题面 查看原题

在前往里约热内卢的路上,奥斯塔普与一只装在特殊盒子里的蚱蜢玩耍,以此消磨时间。 Ostap 构建一条长度为 n 的线,使得该线的某些单元格是空的,而某些单元格包含障碍物。然后,他将蚱蜢放在其中一个空牢房中,并将一只小昆虫放在另一个空牢房中。蚱蜢想吃掉这只昆虫。

Ostap 知道,grasshopper 能够跳到距当前单元格恰好 k 个单元格(向左或向右)的任何空单元格。请注意,当蚱蜢跳过中间单元格时,中间单元格是否为空并不重要。例如,如果 k = 1,则蚱蜢只能跳跃到相邻单元格,如果 k = 2,则蚱蜢可以跳过单个单元格。

您的目标是确定是否存在一系列跳跃,使得蚱蜢能够从其初始位置到达有昆虫的单元格。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1) - 该行中的单元格数量和一只蚱蜢跳跃的长度。

第二行包含长度为n的字符串,由字符“.”、“#”、“G”和“T”组成。特点 '。'表示对应的格子是空的,字符“#”表示对应的格子有障碍物,蚱蜢无法跳到那里。字符“G”表示蚱蜢从该位置开始,最后“T”表示目标昆虫位于该单元格。保证字符“G”和“T”在此行中只出现一次。

输出

如果存在一系列跳跃(每次跳跃长度为 k),使得蚱蜢可以从其初始位置到达昆虫所在的单元格,则在输入的唯一行中打印“YES”(不带引号)。否则,打印“NO”(不带引号)。

示例

输入 #1

5 2
#G#T#

输出 #1

YES

输入 #2

6 1
T....G

输出 #2

YES

输入 #3

7 3
T..#..G

输出 #3

NO

输入#4

6 2
..GT..

输出#4

NO

注意

在第一个示例中,蚱蜢可以向右跳跃一次,以便从单元格 2 到达单元格 4。

在第二个示例中,蚱蜢只能跳到相邻的单元格,但到达昆虫的路是自由的 - 他可以通过向左跳 5 次到达那里。

在第三个示例中,蚱蜢无法进行一次跳跃。

在第四个样本中,蚱蜢只能跳到索引为奇数的单元格,因此他无法到达昆虫。