Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1735. Поход
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 2B) |
| 26/06/2012 | Лето 2012 - 2 (B) |
| 20/07/2016 | Лето 2016 - 12 (E) |
| 23/02/2023 | Базовый уровень: динамическое программирование 1 (проводит BOGAT) (G) |
| 10/07/2023 | Лето 2023-7 простые (C) |
| 27/02/2024 | Динамическое программирование 1 (проводит BOGAT) (G) |
| 08/07/2024 | Лето 2024-7 простые (C) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует
множество притоков, которые могут впадать в нее как с правого, так и с левого берега.
Школьники хотят начать поход в некоторой точке на левом берегу и закончить поход в некоторой
точке на правом берегу, возможно, переправляясь через реки несколько раз. Как известно, переправа
как через реку, так и через приток представляет собой определенную сложность, поэтому они хотят
минимизировать число совершенных переправ.
Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впа-
дают притоки на всем их маршруте.
Помогите школьникам по данному описанию притоков определить минимальное количество пе-
реправ, которое им придется совершить во время похода.
Единственная строка ввода содержит описание Москвы-реки между начальной и конечной точкой похода.
Длина строки не превосходит `10^5` символов.
Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает,
что очередной приток впадает в реку с левого берега, R – приток впадает в реку с правого берега и
B – притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед
описанной частью реки и заканчивается на правом берегу после описанной части.
Выведите одно целое число – минимальное количество переправ.
Рисунок, соответствующий примеру:
Пример ввода
LLBLRRBRL
Пример вывода
5
