Codeforces Round 721 (Div. 2) |
---|
Закончено |
Единственное отличие между простой и сложной версией заключается в том, что $$$s$$$ в простой версии изначально палиндром, что не всегда верно в сложной версии.
Палиндромом называется строка, читающаяся одинаково слева направо и справа налево. Например, «101101» — палиндром, а «0101» — нет.
Алиса и Боб играют в игру со строкой $$$s$$$ длины $$$n$$$ состоящей из символов '0' и '1'. Оба игрока ходят по очереди, и Алиса делает первый ход.
Каждый ход игрок может сделать одну из следующих операций:
Под разворотом строки подразумевается переупорядочивание символов от последнего к первому. Например, «01001» после разворота становится «10010».
Игра заканчивается тогда, когда вся строка состоит из '1'. Игрок, потратившей меньше долларов, побеждает. Если оба игрока потратили одинаковую сумму, то игра завершается ничьей. Выведите результат игры, если оба игрока действуют оптимально.
Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^3$$$). Далее следуют $$$t$$$ наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^3$$$).
Вторая строка набора содержит строку $$$s$$$ длины $$$n$$$, состоящую только из '0' и '1'. Гарантируется, что строка $$$s$$$ содержит минимум один '0'.
Обратите внимание, что ограничения на сумму $$$n$$$ по всем наборам входных данных нет.
Для каждого набора входных данных выведите ответ:
3 3 110 2 00 4 1010
ALICE BOB ALICE
В первом примере,
Во втором примере,
Название |
---|