Алиса и Боб играют в игру. У них есть бинарная строка \(s\) (каждый символ бинарной строки — либо \(0\), либо \(1\)). Алиса ходит первой, потом Боб, потом снова Алиса, и так далее.
В свой ход игрок должен выбрать несколько (не менее одного) последовательных одинаковых символов в \(s\) и удалить их.
Например, если текущая строка — \(10110\), существует \(6\) возможных ходов (удаляемые символы выделены жирным):
- \(\textbf{1}0110 \to 0110\);
- \(1\textbf{0}110 \to 1110\);
- \(10\textbf{1}10 \to 1010\);
- \(101\textbf{1}0 \to 1010\);
- \(10\textbf{11}0 \to 100\);
- \(1011\textbf{0} \to 1011\).
После удаления символов те символы, которые стояли слева и справа от удаленного блока, становятся последовательными. Т. е. следующая последовательность операций возможна: \(10\textbf{11}0 \to 1\textbf{00} \to 1\).
Игра заканчивается, когда строка становится пустой. Счет каждого игрока равен кол-ву символов \(1\), которые он удалил.
Каждый игрок хочет набрать максимально возможное количество очков. Посчитайте, сколько очков наберет Алиса.