457. Доставка от Йолли

Не решаласьСложная

Робот Йолли получил задание доставить посылку из города Альфа в город Бета. Йолли предстоит ехать по оживлённой дороге под названием Звёздный Путь, на которой есть множество мостов-развязок. Город Альфа находится к северу от Звёздного Пути, а город Бета — к югу. Йолли очень не любит пересекать дороги и мосты. К счастью, у него есть карта, и он успел её изучить. Помогите Йолли определить минимальное возможное количество пересечений на своём пути.

Формат ввода

Единственная строка содержит описание Звёздного Пути между точками Альфа и Бета. Длина строки не превосходит 10510^5 символов. Каждый символ строки может быть одной из трёх цифр: 11, 22 или 33.

  • Цифра 11 означает, что есть мост, впадающий в Звёздный Путь слева.
  • Цифра 22 — есть мост, впадающий в Звёздный Путь справа.
  • Цифра 33 — есть мосты, впадающие в Звёздный Путь слева и справа в одном месте.

Формат вывода

Выведите одно число — минимальное возможное количество пересечений на пути Йолли.

Примечание

Точка Альфа расположена перед описанной частью Звёздного Пути. Точка Бета расположена после описанной части.

Условие

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
113122321
Вывод
5

Теги

Нужно войти, чтобы отправить решение.Войти