Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На узкой тропинке встретились лягушки, идущие через болото налево, и лягушки, идущие направо. Тропинка была такая узкая, что лягушкам приходилось перепрыгивать через друг друга, чтобы пройти. Лягушки очень торопились, прыгали туда-сюда, спорили, кто должен идти первым, но только мешали друг другу пройти. В конце концов лягушки совсем перепутались и охрипли от кваканья, и тут одна самая умная лягушка сказала, что лучше сначала всё рассчитать, а затем прыгать.
Напишите программу, определяющую минимальное число ходов, которое должны сделать лягушки, чтобы все лягушки, идущие налево, оказались на левом краю тропинки, а лягушки, идущие направо, – на правом краю тропинки. Ходом считается либо перемещение лягушки на соседнюю пустую кочку, либо последовательность прыжков одной лягушки через других лягушек. Прыжок возможен, если лягушка, через которую происходит прыжок, стоит на соседней кочке, а следующая за ней кочка пустая.
В первой строке входного файла содержится строка, состоящая из символов 'L', 'R' и '.', описывающая текущую ситуацию. Символ 'L' означает кочку с лягушкой, идущей налево, 'R' – кочку с лягушкой, идущей направо, '.' – пустую кочку на тропинке. Строка имеет длину от 2 до 9 символов и содержит как минимум один символ '.'.
В выходной файл вывести одно целое число – минимальное количество ходов.
Порядок ходов: R.LR. –> RL.R. –> .L.RR –> L..RR