printРабочее место участника

printЗадачи

1735. Поход

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега. Школьники хотят начать поход в некоторой точке на левом берегу и закончить поход в некоторой точке на правом берегу, возможно, переправляясь через реки несколько раз. Как известно, переправа как через реку, так и через приток представляет собой определенную сложность, поэтому они хотят минимизировать число совершенных переправ.
Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впа- дают притоки на всем их маршруте.
Помогите школьникам по данному описанию притоков определить минимальное количество пе- реправ, которое им придется совершить во время похода.
Единственная строка ввода содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит `10^5` символов.
Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R – приток впадает в реку с правого берега и B – притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.
Выведите одно целое число – минимальное количество переправ.
Рисунок, соответствующий примеру:
21631.png

Пример ввода

LLBLRRBRL

Пример вывода

5
Источник: Московская олимпиада школьников по информатике, 2011/12 учебный год
loading