Крок Крок Еволюція
Японська компанія з розробки відеоігор створила музичну відеогру під назвою Step Step Evolution. Ігровий процес у Step Step Evolution дуже простий. Гравці стоять на танцювальній платформі та натискають на панелі відповідно до послідовності стрілок, що з'являються на екрані.
У Step Step Evolution є вісім типів стрілок: ВГОРУ, ВГОРУ-ПРАВО, ПРАВО, ВНИЗ-ПРАВО, ВНИЗ, ВНИЗ-ЛІВО, ЛІВО та ВГОРУ-ЛІВО. Ці стрілки рухаються вгору знизу екрана. Коли стрілка досягає нерухомої стрілки вгорі, гравець повинен натиснути відповідну панель на танцювальній платформі. Нижче наведено зображення танцювальної платформи.
Рисунок 1: танцювальна платформа для Step Step Evolution
У грі діють такі правила:
За винятком початку гри, ви не повинні натискати на панель, яка не відповідає заданій стрілці.
Нога повинна залишатися на панелі, де вона була натиснута останній раз, і не переміщатися, поки не буде натиснута наступна панель.
Ліва нога не повинна наступати на панель, яка розташована праворуч від панелі, на якій стоїть права нога. І навпаки, права нога не повинна наступати на панель, яка розташована ліворуч від панелі, на якій стоїть ліва нога.
Щодо третього правила, наступний рисунок показує приклади правильних і неправильних кроків.
Рисунок 2: приклади правильних і неправильних кроків
Перший (ліва нога для ЛІВО, права нога для ВНИЗ) і другий (ліва нога для ВНИЗ-ЛІВО, права нога для ВГОРУ-ЛІВО) є правильними кроками. Останній (ліва нога для ПРАВО, права нога для ВНИЗ) є неправильним кроком.
Зверніть увагу, що на початку гри ліва і права нога можуть бути розміщені будь-де на панелі. Також ви можете почати перший крок з лівої або правої ноги, як вам зручно.
Щоб грати в цю гру красиво, стиль гри, відомий як "Природний стиль кроків", є загальновідомим серед талановитих гравців. "Природний стиль кроків" - це стиль, у якому гравці роблять кроки по черзі лівою і правою ногою. Однак, коли послідовність стрілок складна, гравці іноді змушені порушувати цей стиль.
Тепер ваш друг створив для вас послідовність стрілок, які потрібно натискати. Вас цікавить, скільки разів вам доведеться порушити "Природний стиль кроків", коли ви оптимально граєте з цією послідовністю. Іншими словами, яка мінімальна кількість разів, коли вам доведеться наступити на дві послідовні стрілки, використовуючи ту саму ногу?
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних задається одним рядком, що містить послідовність стрілок. Напрямки описуються числами від 1 до 9, за винятком 5. Нижче наведено рисунок, що показує відповідність між числами та стрілками.
Ви можете припустити, що довжина послідовності знаходиться в межах від 1 до 100000, включно. Також стрілки одного напрямку не з’являтимуться підряд у рядку. Кінець вводу позначається одним символом "#".
Рисунок 3: відповідність чисел стрілкам
Вихідні дані
Для кожного набору даних виведіть, скільки разів вам доведеться порушити "Природний стиль кроків", коли ви граєте оптимально, в одному рядку.