CF1769D2.Игра в Девятку II

В этой версии задачи игроки начинают играть не только на победу, но и на оптимизацию результата игры для них. Вводится понятие величины важности первого хода, и нужно найти $13$ раскладов с различными значениями этой величины.

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

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

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

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

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

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

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

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

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

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

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

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

在此题目的这一版本中，玩家不仅以获胜为目标，还力求优化自身的游戏结果。我们引入“先手重要性”的概念，并需要找出 $13$ 种具有不同“先手重要性”值的牌局配置。

爱丽丝和鲍勃决定玩一种名为“九”的纸牌游戏。请仔细阅读题目条件，因为其规则可能与您所熟知的有所不同。

游戏使用一副标准的 $36$ 张牌：四种花色（梅花、方块、黑桃、红桃），每种花色各 $9$ 张牌（从六到 A）。按点数由小到大排列顺序为：六、七、八、九、十、J（杰克）、Q（皇后）、K（国王）、A（王牌）。

游戏开始前，整副牌被充分洗匀，然后每位玩家各发 $18$ 张牌。玩家需按照特定规则，依次将手中牌打出至桌面。首先将手中所有牌全部打出的玩家获胜。

两位玩家轮流行动。每次行动有以下三种合法方式之一：

• 从手牌中打出任意花色的一张 九；
• 从手牌中打出任意花色的一张 六、七或八，前提是桌面上已存在同花色且点数高一阶的牌（即分别对应七、八、九）；
• 从手牌中打出任意花色的一张 十、J、Q、K 或 A，前提是桌面上已存在同花色且点数低一阶的牌（即分别对应九、十、J、Q、K）。

例如：黑桃九可在任意时刻打出；要打出梅花七，则桌面上必须已有梅花八；要打出红桃 A，则桌面上必须已有红桃 K。

若某位玩家无法从手牌中合法打出任何一张牌，则轮到对手行动。请注意：不允许无故跳过回合——只要存在至少一种合法出牌方式，就必须执行一次合法出牌。

除力争率先清空手牌外，爱丽丝和鲍勃还希望：在游戏结束时，对手剩余的手牌尽可能多，而自己剩余的手牌尽可能少。再次强调：游戏在任意一名玩家打出其最后一张手牌的瞬间立即结束。

我们将游戏的结果定义为一个组合信息，包含两项内容：（1）在双方均采取最优策略的前提下，哪位玩家获胜；（2）失败方在游戏结束时手中剩余的牌数。

假设爱丽丝和鲍勃均已拿到各自的 $18$ 张手牌，但尚未决定谁执先手。对于该特定牌局配置，我们定义其先手重要性为：当爱丽丝先手时的游戏结果，与当鲍勃先手时的游戏结果，二者之间的绝对差值。

例如：若两种情况下鲍勃均获胜，但在一种情形下爱丽丝终局手牌余 $6$ 张，另一种情形下仅余 $2$ 张，则该牌局的先手重要性为 $4$；又如：一种情形下爱丽丝获胜且鲍勃终局手牌余 $5$ 张，另一种情形下鲍勃获胜且爱丽丝终局手牌余 $3$ 张，则该牌局的先手重要性为 $8$。

两人想了解：不同牌局配置下的“先手重要性”究竟可以相差多大？给定整数 $k \le 13$，请帮助他们找出 $k$ 种牌局配置，使得这 $k$ 种配置对应的先手重要性两两互异，且均为整数。

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

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

在单独的一行中给出一个整数 $k$（$2 \le k \le 13$）——所需排列的数量。

本题包含两个测试用例：第一个测试用例中 $k = 2$，第二个测试用例中 $k = 13$。

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

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

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

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

输出 $k$ 对字符串。每对字符串需对应一个合法的发牌方案。所有输出的发牌方案中，先手重要性值（即 first move importance）必须是互不相同的整数。

在每对字符串的第一行中，请输出 $18$ 个长度为 $2$ 的字符串，以空格分隔，描述爱丽丝所持的 $18$ 张牌，顺序任意。每个字符串的第一个字符表示牌的点数，取自集合 {6, 7, 8, 9, T, J, Q, K, A}，分别代表六、七、八、九、十、杰克（J）、皇后（Q）、国王（K）和王牌（A）；第二个字符表示牌的花色，取自集合 {C, D, S, H}，分别代表梅花（Clubs）、方块（Diamonds）、黑桃（Spades）和红桃（Hearts）。

在每对字符串的第二行中，请以相同格式输出 $18$ 个长度为 $2$ 的字符串，以空格分隔，描述鲍勃所持的 $18$ 张牌。

全部 $36$ 种可能的牌（即 $9$ 种点数 $\times 4$ 种花色）必须恰好各出现一次，且每张牌仅属于两名玩家中的一人。

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

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

在第一个给出的牌局中，所有9都在爱丽丝手中。即使鲍勃先手，他也必须跳过自己的第一个回合。因此，在该牌局中，先手的重要性为 $0$。

在第二个给出的牌局中，无论谁先手，爱丽丝都将获胜。然而，如果爱丽丝先手，则游戏结束时鲍勃手中将剩余1张牌；而如果爱丽丝后手，则鲍勃手中将剩余5张牌。因此，该牌局中先手的重要性为 $4$。