Решение задачи Фафа и ворота с Codeforces

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


Два соседних королевства решили построить на границе стену, но сделать в ней несколько ворот, чтобы жители могли проходить из одного королевства в другое. Как водится, каждый раз, когда житель проходит через ворота, он должен заплатить одну серебряную монету.

Мир может быть представлен как первый квадрант на плоскости, тогда стена построена на прямой x = y. Все точки ниже стены принадлежат одному королевству, все точки выше стены принадлежат другому королевству. В каждой точке стены с целочисленными координатами (т. е. в точках (0, 0), (1, 1), (2, 2), ...) есть ворота. Стена и ворота не принадлежат ни одному королевству.

Фафа находится у ворот в точке (0, 0) и планирует пройтись определенным маршрутом по плоскости. Он знает последовательность своих шагов S. Каждый символ в последовательности описывает одно перемещение. Каждое перемещение — это либо буква 'U' (перемещение вверх, из точки (x, y) в точку (x, y + 1)), либо 'R' (перемещение вправо, из точки (x, y) в точку (x + 1, y)).

Фафа хочет узнать, сколько серебряных монет он должен заплатить, чтобы пройтись по маршруту S. Обратите внимание, если Фафа посещает ворота, но не переходит в другое королевство, он не должен платить. Также, считайте, что он не платит у ворот в точке (0, 0), т. е. он изначально на нужной ему стороне.

Код

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
int main()
{
	cin>>n>>s;
	for(int i=0,x=0,y=0; i!=s.size(); ++i)
	{
		if(s[i]=='U')++y;
		if(s[i]=='R')++x;
		if(y==x&&i+1!=s.size()&&s[i]==s[i+1])++ans;
	}
	cout<<ans;
}

         

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



Комментарии

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