ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрФУ среди юниоров 2016

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Игра с полоской

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Есть двусторонняя полоска 1 × n. Каждый квадратик полоски (всего их 2n, по n с каждой стороны) покрашен в один из двух цветов (назовем их A и B). Алиса и Боб играют в игру. Алиса ходит первой. На каждом ходу игрок может согнуть полоску пополам, при этом сгиб должен проходить по делениям квадратиков (т.е. ход возможен, только если длина полоски чётна). Сгибать полоску можно как вовнутрь, так и наружу. Если после очередного сгиба полоска стала полностью одноцветной, то выигрывает тот игрок, чей это цвет (A соответствует Алисе, B — Бобу). Если же у текущего игрока нет возможных ходов, но никто не выиграл, игра заканчивается ничьей.
Кто выиграет, если игроки играют оптимально? Это означает, что каждый игрок стремится выиграть; если же это невозможно, то добиться ничьей.

Исходные данные

В первой строке вводится целое число n — длина полоски (1 ≤ n ≤ 5 · 105).
Дальше вводятся две строки из букв «A» и «B» длины n, описывающие разные стороны полоски. При этом символы, находящиеся друг под другом, соответствуют разным сторонам одного квадратика.

Результат

Если выиграет Алиса, выведите «Alice». Если выигрывает Боб, выведите «Bob». Если игра завершится ничьей, выведите «Draw».

Примеры

исходные данныерезультат
4
BBAA
BABB
Bob
3
AAA
BBB
Draw
2
AA
BB
Alice

Замечания

В первом примере Алиса начинает игру с полоской BBAA/BABB. После своего хода она может получить полоску BB/AA или BB/AB. В обоих случаях Боб может выиграть, получив полоску B/B.
Во втором примере Алиса не может сделать даже первый ход, поэтому результат — ничья.
В третьем примере Алиса выигрывает первым ходом, получая из полоски AA/BB полоску A/A.
Автор задачи: Никита Сивухин
Источник задачи: Чемпионат УрФУ среди юниоров 2016
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2104. Игра с полоской