Codeforces Round 465 (Div. 2) |
---|
Закончено |
Два соседних королевства решили построить на границе стену, но сделать в ней несколько ворот, чтобы жители могли проходить из одного королевства в другое. Как водится, каждый раз, когда житель проходит через ворота, он должен заплатить одну серебряную монету.
Мир может быть представлен как первый квадрант на плоскости, тогда стена построена на прямой 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), т. е. он изначально на нужной ему стороне.
Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — количество перемещений в последовательности.
Во второй строке находится строка S длины n, состоящая из символов 'U' и 'R', описывающая перемещения. Фафа будет следовать этой последовательности S в порядке слева направо.
В единственной строке выведите одно целое число — количество монет, которое должен заплатить Фафа, чтобы пройти по последовательности S.
1
U
0
6
RURUUR
1
7
URRRUUU
2
Рисунок ниже показывает третий пример. Красным показан путь Фафы, зеленые точки отмечают ворота, в которых Фафа должен заплатить монету.
Название |
---|