ACM 2006 - Fool Game

Problem Q. Fool Game ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	Far-Eastern Subregional	Time limit:	3 sec
Input file:	input.txt	Memory limit:	8 Mb
Output file:	output.txt

Statement

The game of fool is played with a small set of cards, which includes nine ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a trump. During the game, the card beats another card, if either it has the same suit and higher rank, or it is a trump, while the beaten card is not.

In the game, a move proceeds as following. First player puts one of his cards on the desk, and the second player can either beat it with one of his cards, putting his card over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in any of his remaining cards, which has same rank as any card already on the desk. This card, in turn, may be beaten or taken together with all other cards on the desk, etc. For example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten with 7h, so the second player has to take it.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

If there is more than one such move, the program must find one with smallest rank. If there is several moves with smallest rank, program must choose the card with the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the example above, second player could beat Kd with 7h, thus preventing further flips. On the other hand, move of Qh will be immediately taken.

Input file format

In the first line of input file there is a single character h, s, d, or c, determining a trump suit. On the second line there is a string denoting first playerTs cards, and on the third line S the string with the second playerTs cards. All cards are different, and the players have equal number of cards.

Output file format

Output file must contain a single line with either a card to move or a string "NO", if a program was unable to find it.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`s As7h8dJc Jd8s7c0c`	`7h`