D1. Игра в Девятку I
*special; brute force; dp
В этой версии задачи нужно определить, кто выиграет в карточной игре для двух игроков в заданном раскладе при оптимальной игре обоих соперников.Алиса и Боб решили сыграть в карточную игру «Девятка». Пожалуйста, внимательно прочитайте условие задачи, поскольку правила могут отличаться от известных вам.Для игры нужна стандартная колода из \(36\) карт — по девять карт (от шестёрки до туза) каждой из четырёх мастей (трефы, бубны, пики и черви). Карты по достоинству от младшей к старшей идут следующим образом: шестёрка, семёрка, восьмёрка, девятка, десятка, валет, дама, король, туз.Перед игрой колода перемешивается, и каждому игроку раздаётся по \(18\) карт. Карты нужно выкладывать из руки на стол по определённым правилам. Выигрывает игрок, который первым выложит все карты из своей руки.Игроки ходят по очереди. Ход игрока имеет один из следующих видов: выложить на стол из своей руки девятку любой масти; выложить на стол шестёрку, семёрку или восьмёрку любой масти, если на столе уже лежит карта той же масти достоинством на единицу выше; выложить на стол десятку, валета, даму, короля или туза любой масти, если на столе уже лежит карта той же масти достоинством на единицу ниже. Например, девятку пик можно выложить на стол в любой момент, для выкладывания семёрки треф необходимо наличие на столе восьмёрки треф, а для выкладывания туза червей необходимо наличие на столе короля червей.Если игрок не может выложить на стол ни одну карту из своей руки, то ход переходит к сопернику. Обратите внимание: нельзя пропустить ход просто так — всегда необходимо выложить карту на стол корректным образом, если это возможно.Вам дан расклад карт в начале игры. Алиса будет ходить первой. Определите, кто первым избавится от всех своих карт и выиграет, если оба игрока будут пытаться победить и играть оптимально.
В первой строке задано \(18\) строк длины \(2\) через пробел, описывающих карты Алисы в случайном порядке. Первый символ строки обозначает достоинство карты — символ из набора 6, 7, 8, 9, T, J, Q, K, A, обозначающий шестёрку, семёрку, восьмёрку, девятку, десятку, валета, даму, короля и туза, соответственно. Второй символ строки обозначает масть карты — символ из набора C, D, S, H, обозначающий трефы, бубны, пики и черви, соответственно.Во второй строке задано \(18\) строк длины \(2\) через пробел, описывающих карты Боба в том же формате.Каждая из \(36\) возможных карт находится в руке одного из двух игроков в единственном экземпляре.В задаче \(100\) тестов. Все тесты сгенерированы случайным образом.
Выведите Alice, если при оптимальной игре выиграет Алиса, и Bob в противном случае.