Игра в Девятку III
Contest: VK Cup 2022 - Квалификация (Engine)
Difficulty rating: 2300
Tags: *special, brute force

В этой версии задачи нужно найти $$$26$$$ раскладов с различными значениями важности первого хода.

Алиса и Боб решили сыграть в карточную игру «Девятка». Пожалуйста, внимательно прочитайте условие задачи, поскольку правила могут отличаться от известных вам.

Для игры нужна стандартная колода из $$$36$$$ карт — по девять карт (от шестёрки до туза) каждой из четырёх мастей (трефы, бубны, пики и черви). Карты по достоинству от младшей к старшей идут следующим образом: шестёрка, семёрка, восьмёрка, девятка, десятка, валет, дама, король, туз.

Перед игрой колода перемешивается, и каждому игроку раздаётся по $$$18$$$ карт. Карты нужно выкладывать из руки на стол по определённым правилам. Выигрывает игрок, который первым выложит все карты из своей руки.

Игроки ходят по очереди. Ход игрока имеет один из следующих видов:

- выложить на стол из своей руки девятку любой масти;
- выложить на стол шестёрку, семёрку или восьмёрку любой масти, если на столе уже лежит карта той же масти достоинством на единицу выше;
- выложить на стол десятку, валета, даму, короля или туза любой масти, если на столе уже лежит карта той же масти достоинством на единицу ниже.

Например, девятку пик можно выложить на стол в любой момент, для выкладывания семёрки треф необходимо наличие на столе восьмёрки треф, а для выкладывания туза червей необходимо наличие на столе короля червей.

Если игрок не может выложить на стол ни одну карту из своей руки, то ход переходит к сопернику. Обратите внимание: нельзя пропустить ход просто так — всегда необходимо выложить карту на стол корректным образом, если это возможно.

Помимо того, что каждый игрок стремится избавиться от карт в своей руке, Алиса и Боб также хотят, чтобы в конце игры в руке у их соперника карт осталось как можно больше, а в их руке — как можно меньше. Напомним, что игра заканчивается, как только один из игроков выкладывает на стол последнюю карту из своей руки.

Результатом игры назовём совокупность из информации о том, кто из двух игроков выиграет при оптимальной игре, а также о том, сколько карт останется в руке у проигравшего.

Пусть Алиса и Боб уже взяли в руки свои $$$18$$$ карт каждый, но ещё не решили, кто из них будет ходить первым. Величиной важности первого хода для данного расклада назовём абсолютную разность между результатами игры в случае, если первой будет ходить Алиса, и в случае, если первым будет ходить Боб.

Например, если в обоих случаях выиграет Боб, но в одном случае у Алисы останется $$$6$$$ карт в руке в конце игры, а во втором — всего $$$2$$$, то величина важности первого хода равна $$$4$$$. Если же в одном случае выиграет Алиса и у Боба останется $$$5$$$ карт в руке, а во втором случае выиграет Боб и у Алисы останется $$$3$$$ карты в руке, то величина важности первого хода равна $$$8$$$.

Ребята хотят узнать, насколько разной бывает величина важности первого хода для разных раскладов. По заданному числу $$$k \le 26$$$ помогите им найти такие $$$k$$$ раскладов, что величины важности первого хода для всех них — различные целые числа.

Input format:
В единственной строке задано целое число $$$k$$$ ($$$2 \le k \le 26$$$) — число необходимых раскладов.

В задаче три теста. В первом тесте $$$k = 2$$$, во втором тесте $$$k = 13$$$, в третьем тесте $$$k = 26$$$.

Output format:
Выведите $$$k$$$ пар строк. Каждая пара строк должна соответствовать некоторому раскладу. Величины важности первого хода для всех выведенных раскладов должны быть различными целыми числами.

В первой строке каждой пары выведите $$$18$$$ строк длины $$$2$$$ через пробел, описывающих карты Алисы в любом порядке. Первый символ строки должен обозначать достоинство карты — символ из набора 6, 7, 8, 9, T, J, Q, K, A, обозначающий шестёрку, семёрку, восьмёрку, девятку, десятку, валета, даму, короля и туза соответственно. Второй символ строки должен обозначать масть карты — символ из набора C, D, S, H, обозначающий трефы, бубны, пики и черви соответственно.

Во второй строке выведите $$$18$$$ строк длины $$$2$$$ через пробел, описывающих карты Боба в том же формате.

Каждая из $$$36$$$ возможных карт должна находиться в руке одного из двух игроков в единственном экземпляре.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
В первом выведенном раскладе все девятки находятся в руке у Алисы. Даже если Боб будет ходить первым, ему всё равно придётся пропустить первый же свой ход. Следовательно, первый ход при таком раскладе имеет важность $$$0$$$.

Во втором выведенном раскладе вне зависимости от того, чьим будет первый ход, выиграет Алиса. Однако если Алиса будет ходить первой, то у Боба в конце игры в руке останется одна карта, а если же она будет ходить второй, то у Боба останется пять карт. Соответственно, величина важности первого хода при таком раскладе равна $$$4$$$.

Example input:
2

Example output:
KS QD 8D QC 8S 8C JD 9H AC TH 9S 9D QH 7H 8H TS 7S 9C
6D JS 7D KH QS TC AD AS KC 6C 7C TD AH KD 6S JC JH 6H

JC JS 8S TD JD KH 7D 9C KC TH QD 8D 7H TC KD 9H 8C 6D
7S AC QH AD 8H TS 6H JH 6C AH 7C 6S 9D QC AS QS KS 9S

Editorial:
Первая версия задачи представляет собой игру с нулевой суммой и полной информацией. Позиция в игре задаётся множеством выложенных на стол карт и тем, чей сейчас ход (множество карт в руке каждого игрока вычисляется из этой информации однозначным образом). Все возможные позиции образуют ориентированный граф, где из каждой позиции проведены дуги во все позиции, в которые текущий игрок может перейти за один ход. Кроме того, если текущий игрок не может сделать ни одного хода, то из позиции есть ровно одна дуга — в позицию с тем же множеством выложенных карт и ходом другого игрока. Заметим, что в ситуации, когда у обоих игроков есть карты в руке, хотя бы один из них всегда может сделать ход, а также то, что число выложенных на стол карт постоянно увеличивается — значит, граф является ацикличным.
Для каждой позиции можно определить, выигрышная она или проигрышная для текущего игрока, следующим образом. Если у одного игрока закончились карты, то он выиграл. Иначе посмотрим на все дуги, ведущие из позиции. Если все они ведут в позиции, выигрышные для соперника текущего игрока, то сама позиция является проигрышной для текущего игрока. В противном случае позиция является выигрышной, так как текущий игрок может сделать ход в любую из проигрышных для соперника позиций.
Определять выигрышность позиций можно либо в порядке обратной топологической сортировки графа, либо же лениво, при помощи рекурсии с запоминанием.
Осталось оценить размер графа. Заметим, что в каждой масти в любой момент времени либо не выложено ни одной карты, либо же выложенные карты образуют отрезок, который начинается с шестёрки, семёрки, восьмёрки или девятки, а заканчивается девяткой, десяткой, валетом, дамой, королём или тузом. Значит, в каждой масти есть $$$1 + 4 \cdot 6 = 25$$$ возможных множеств выложенных карт, а всего позиций тогда не более $$$25^4 \cdot 2 = 781\,250$$$ — следовательно, наш граф не слишком велик, и можно позволить себе рассмотреть все его состояния.
Во второй версии задачи игра становится сложнее, поскольку игроки теперь также стремятся избавляться от карт и мешать сопернику делать то же самое. Тем не менее, основная часть решения остаётся такой же, а отличие заключается лишь в том, какое значение мы вычисляем для каждой позиции.
Вместо одного бита — выигрышная позиция или проигрышная — будем теперь хранить целое число. Если текущий игрок выигрывает, то значение будет равняться числу карт в руке соперника в конце игры. Если же игрок проигрывает, то значение будет равняться числу карт в его руке в конце игры, но со знаком «минус». Тогда получится, что каждый игрок стремится к максимизации этого значения для себя.
Результат игры в позиции можно вычислить следующим образом: посмотрим на все результаты игр в позициях, в которые ведут дуги, инвертируем знак во всех из них (поскольку это значения для нашего соперника) и возьмём максимум.
Как теперь вычислить величину важности первого хода? Найдём результат игры $$$r_1$$$ в позиции, где карт на столе нет и ходит Алиса, и результат игры $$$r_2$$$ в позиции, где карт на столе нет и ходит Боб. Тогда величина важности первого хода равна $$$|r_1 - (-r_2)| = |r_1 + r_2|$$$.
Для прохождения второй версии задачи достаточно было генерировать случайные расклады, вычислять величину важности первого хода для каждого из них и собирать уникальные найденные результаты в множестве, пока размер этого множества не достигнет $$$13$$$.
Перейдём к третьей версии задачи. Найти $$$26$$$ раскладов с разными величинами случайной стратегией довольно сложно. Заметим, что для случайных раскладов искомая величина обычно весьма мала. Как же найти расклад с большой величиной?
Обратим внимание на такой расклад: в двух мастях у Алисы есть все карты, кроме девятки, а в двух других мастях — наоборот, только девятка. Расклад симметричен, и ходить первым в таком раскладе крайне невыгодно — у того игрока, который ходит первым, в конце игры останется $$$15$$$ карт в руке. Следовательно, величина важности первого хода для этого расклада равна $$$30$$$.
Теперь вместо того, чтобы генерировать полностью случайные расклады, будем вносить небольшое число случайных изменений в расклад из предыдущего абзаца — например, менять одну-две-три случайные карты между начальными руками игроков. Таким образом можно найти расклады, в которых величина важности первого хода велика, но меньше $$$30$$$.
В действительности существует $$$27$$$ различных значений важности первого хода: все значения от $$$0$$$ до $$$24$$$, а также $$$26$$$ и $$$30$$$.