- Описание
- Отправленные решения
457. Доставка от Йолли
Робот Йолли получил задание доставить посылку из города Альфа в город Бета. Йолли предстоит ехать по оживлённой дороге под названием Звёздный Путь, на которой есть множество мостов-развязок. Город Альфа находится к северу от Звёздного Пути, а город Бета — к югу. Йолли очень не любит пересекать дороги и мосты. К счастью, у него есть карта, и он успел её изучить. Помогите Йолли определить минимальное возможное количество пересечений на своём пути.
Формат ввода
Единственная строка содержит описание Звёздного Пути между точками Альфа и Бета. Длина строки не превосходит символов. Каждый символ строки может быть одной из трёх цифр: , или .
- Цифра означает, что есть мост, впадающий в Звёздный Путь слева.
- Цифра — есть мост, впадающий в Звёздный Путь справа.
- Цифра — есть мосты, впадающие в Звёздный Путь слева и справа в одном месте.
Формат вывода
Выведите одно число — минимальное возможное количество пересечений на пути Йолли.
Примечание
Точка Альфа расположена перед описанной частью Звёздного Пути. Точка Бета расположена после описанной части.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
113122321
5