Problem G
Cheating at War
War is a classic and very simple two-player card game played with a standard $52$-card deck. The deck is shuffled and split into two equal-sized piles, one for each player, with cards face down. To play, both players turn over the top card of their draw pile. The player whose card rank is higher (suit doesn’t matter) wins both cards. In our variant of War for this problem, when a tie in rank occurs, both players take their one card back.1 The ranks of the cards, from highest to lowest, are [A]ce, [K]ing, [Q]ueen, [J]ack, [T]en, $9$, $8$, $7$, $6$, $5$, $4$, $3$, and $2$. After the card battle is settled, both players would turn over the next card in their draw piles for the following battle, and so forth. Also in our variant, after the initial $26$-card piles have been exhausted, both players count the cards they have won, and the player with the most cards wins the game.
Yraglac found himself playing War with a friend, and the first ten card battles of a game went like this:
![\includegraphics[width=0.9\textwidth ]{figure-war.pdf}](/problems/cheatingatwar/file/statement/en/img-0001.png)
At this point in the game, Yraglac would have won a total of
$10$ cards.
After a few games, Yraglac was bored out of his mind because the game, clearly, has absolutely no element of strategy whatsoever! At the beginning of the next game, when his friend wasn’t looking, he decided to take a peek through both piles of cards and wondered, “How many cards could I win if I could rearrange my own pile of cards?” Now there’s a challenge worthy of his mighty brain!
It turned out for Yraglac that cheating at War was a little harder than he initially thought. Can you help by writing a program that, given lists of the cards in Yraglac’s opponent’s pile and in his own pile, determines the most cards Yraglac can win if he could rearrange the cards in his draw pile in any order he likes?
Input
The first line of the input contains a single integer,
$1 \leq N \leq 50$,
indicating the number of games of war to be played. Following,
there are two lines of input for each game. The first of the
two lines contains a $26$-character string indicating the
cards in the opponent’s pile, in the order that they will be
played. Non-numeric cards are encoded with a single capital
letter as described in the problem statement. The second of the
two lines indicates the $26$ cards in Yraglac’s pile. Both
piles together will always form the set of cards in a standard
$52$-card deck.
Output
For each game of War described in the input, output on a single line the highest number of cards Yraglac can win if he were able to rearrange his pile of cards to be played in any order.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3J665T72457Q2J3AA9K3TK7T5A 296K979725JQA3K686679KT338 AKQJT98765432AKQJT98765432 AKQJT98765432AKQJT98765432 AAAAKKKKQQQQJJJJTTTT999988 22223333444455556666777788 |
42 48 2 |
Footnotes
- In the usual variants of War, a tie would incite a “war”, and both players would play an additional face-down card followed by another face-up card. The player with the higher face-up card would win all six cards in the war. Cards won would also be returned to the bottom of the respective player’s draw pile, potentially making for a very long game.
