Единственное отличие между простой и сложной версией заключается в том, что \(s\) в простой версии изначально является палиндромом, что не всегда верно в сложной версии.
Палиндромом называется строка, читающаяся одинаково слева направо и справа налево. Например, «101101» — палиндром, а «0101» — нет.
Алиса и Боб играют в игру со строкой \(s\) (которая изначально является палиндромом в простой версии) длины \(n\), состоящей из символов '0' и '1'. Оба игрока ходят по очереди, и Алиса делает первый ход.
За один ход игрок может сделать одну из следующих операций:
- Выбрать любое \(i\) (\(1 \le i \le n\)) такое, что \(s[i] =\) '0', заменить \(s[i]\) на '1' и заплатить 1 доллар, или
- Развернуть всю строку, заплатив 0 долларов. Эта операция доступна только в том случае, если сейчас строка не палиндром, и последняя операция была не разворотом. Это значит, что если Алиса развернула строку, то Боб не может развернуть ее следующим ходом, и наоборот.
Под разворотом строки подразумевается переупорядочивание символов от последнего к первому. Например, «01001» после разворота становится «10010».
Игра заканчивается тогда, когда вся строка состоит из '1'. Игрок, потративший меньше долларов, побеждает. Если оба игрока потратили одинаковую сумму, то игра завершается ничьей. Выведите результат игры, если оба игрока действуют оптимально.