NWERC11H - Tichu


Tichu is a card game played by four players. The players sit around a square table, and each player forms a team with the person sitting opposite him or her. The game is played with a standard deck of cards and four additional special cards. The basic rule of the game is as follows: the player who won the last trick can start a new trick with any legal combination of cards. Then, in turn, each next player can either pass or play the same combination of cards, but with a higher value. This continues until everyone passes, and at that point the player who played the last combination wins the trick and can start a new trick. The main goal is to get rid of all of your cards as soon as possible.

These basic rules make it a good tactic to combine the cards in such a way that they can be played in as few combinations as possible. For simplicity we consider here a slightly modified version of the game. We ignore the special cards, so that leaves a standard deck of 52 cards, ranging over the values 2 to Ace and over the suits hearts, diamonds, clubs, and spades. The suits are indicated by the lowercase letters h, d, c, and s, while the values are indicated in increasing order by 29, T, J, Q, K, A.

The following list is a complete set of legal combinations:1

  • any single card;
  • a pair of cards of the same value;
  • three cards of the same value;
  • four cards of the same value;
  • a full house, that is, three cards of the same value and two cards of another, same value, for example 444KK;
  • a straight of length at least five, that is, at least five cards of consecutive increasing values, for example 89TJQK.

In this problem, your task is to determine the minimum number of combinations that your hand of 13 cards can be partitioned into.



On the first line a positive integer: the number of test cases, at most 100. After that per test case:

  • one line that describes your hand of 13 cards. A card is described by two characters: the value followed by the suit. All cards in your hand are different.



Per test case:

  • one line containing an integer n: the minimum number of combinations that your hand can be partitioned into.
  • n lines that describe a minimal set of combinations of cards from your hand. Each line should contain the cards in one legal combination, in the same format as in the input. All cards from your hand must occur exactly once in one of the combinations. No specific ordering of the combinations or the cards within a combination is required.


Sample in- and output



2h 3c 4d 5d 6s Th Qc Qs Ad Tc Ts 9c 9d
2h 3h 4h 5h 6d 7s 8h 8d 8c 8s 9c Td Js
2h 3c 4d 5d 6s
Th Ts Tc Qc Qs
9d 9c
2h 3h 4h 5h 6d 7s 8d 9c Td Js
8h 8s 8c 

1Those who know the game of Tichu might have noticed that we removed consecutive pairs of cards as a valid combination.

Copyright notice

This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode

Added by:Jeroen Bransen
Time limit:0.509s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NWERC 2011 Jury

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.