Як увімкнути телевізор?
Limits: 2 sec., 256 MiB
Зима близько. А Зеник та Марічка купили собі будинок та освоюються в ньому.
Виявляється, попередні власники будинку думали, що встановлення великої кількості вимикачів підряд допоможе заощаджувати електроенергію, та це не так. Але Зенику та Марічці тепер приходиться з цим жити.
Щоб увімкнути якийсь прилад потрібно пройти цілий квест. Наприклад, за вимкнення телевізора відповідають n вимикачів, під’єднаних один за одним.
Кожен із вимикачів має форму квадрата, і може перебувати в одному з двох станів:
струм може перетікати від верхнього лівого кута до нижнього правого (такий стан позначимо
\
),струм може перетікати від нижнього лівого кута до верхнього правого (такий стан позначимо
/
).
Усі вимикачі розташовані горизонтально в один ряд. Для кожної пари сусідніх вимикачів верхній правий та нижній правий кут лівого вимикача мають електричні з’єднання з верхнім лівим та нижнім лівим кутами правого вимикача відповідно. Дивіться ілюстрацію до прикладу в розділі Примітки для кращого розуміння.
Також струм підведено до обох входів першого вимикача, а обидва виходи останнього вимикача під’єднані до телевізора.
Зенику відомо у якому стані зараз перебувають усі вимикачі. А яку мінімальну кількість вимикачів потрібно перемкнути, щоб електричний струм потрапив до телевізора і можна було його увімкнути?
Input
У першому рядку задано єдине число n — кількість вимикачів.
У другому рядку задано рядок s
довжини n який описує стани усіх
вимикачів. Якщо si=
\
, то i-й вимикач
зараз у першому стані, а якщо si=
/
, то у другому.
Output
Виведіть одне число — мінімальну кількість вимикачів, які потрібно перемкнути, щоб увімкнути телевізор.
Constraints
2≤n≤105,
s складається виключно з
символів /
та \
.
Оцінювання задачі складається із наступних блоків:
1 бал — перший приклад з умови,
1 бал — другий приклад з умови,
13 балів — блок тестів у яких 1≤n≤10,
40 балів — блок тестів у яких 11≤n≤1000,
45 балів — блок тестів у яких 1001≤n≤105.
Бали за блок ви отримаєте, лише якщо дасте правильну відповідь на всі тести з блоку.
Samples
Input (stdin) | Output (stdout) |
---|---|
5 /\/// | 1 |
Input (stdin) | Output (stdout) |
---|---|
3 //\ | 1 |
Notes
Як видно з рисунка — з першого вимикача струм перетікає до другого та з другого до третього. Позиція четвертого вимикача не дозволяє струму перетікати далі.
Але якщо перемкнути лише четвертий вимикач — струм перетече з третього до четвертого, з четвертого до п’ятого, а з п’ятого — до телевізора.