Решение задачи Остап и Кузнечик с Codeforces

Без пояснения   Просмотров: 107

В пути до Рио-де-Жaнeйро Остап развлекается, играя с кузнечиком, которого он взял с собой в специальной коробочке. Остап строит для кузнечика полосу препятствий длиной n, некоторые клетки полосы свободные, а другие полностью заняты. В одну из свободных клеток Остап помещает кузнечика, а в другую — маленькое насекомое, которое кузнечик хочет съесть.

Известно, что за один прыжок кузнечик может переместиться в любую свободную клетку на расстоянии в точности k от текущей, при этом для прыжка кузнечика не имеет значения, свободны или пусты промежуточные клетки. Например, если k = 1, то кузнечик может прыгать только в соседнюю клетку, а если k = 2, то через клетку.

Определите, существует ли последовательность корректных прыжков, которая приводит кузнечика в клетку с насекомым.

Код 

#include<bits/stdc++.h>
using namespace std;
int n,k,p;
string s;
int main()
{
	cin>>n>>k>>s;
	for(int i=0;i<n;i++)
		if(s[i]=='G')
			p=i;
	for(int i=p;i<n;i+=k)
	{
		if(s[i]=='#')
			i=n;
		else if(s[i]=='T')
		{
			cout<<"YES";
			return 0;
		}
	}
	for(int i=p;i>=0;i-=k)
	{
		if(s[i]=='#')
			i=0;
		else if(s[i]=='T')
		{
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта