codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1932D.md (2806B)


      1 Source: https://codeforces.com/problemset/problem/1932/D
      2 
      3 D. Card Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Two players are playing an online card game. The game is played using a 32-card deck. Each card has a suit and a rank. There are four suits: clubs, diamonds, hearts, and spades. We will encode them with characters 'C', 'D', 'H', and 'S', respectively. And there are 8 ranks, in increasing order: '2', '3', '4', '5', '6', '7', '8', '9'.
     22 
     23 Each card is denoted by two letters: its rank and its suit. For example, the 8 of Hearts is denoted as 8H.
     24 
     25 At the beginning of the game, one suit is chosen as the trump suit.
     26 
     27 In each round, players make moves like this: the first player places one of his cards on the table, and the second player must beat this card with one of their cards. After that, both cards are moved to the discard pile.
     28 
     29 A card can beat another card if both cards have the same suit and the first card has a higher rank than the second. For example, 8S can beat 4S. Additionally, a trump card can beat any non-trump card, regardless of the rank of the cards, for example, if the trump suit is clubs ('C'), then 3C can beat 9D. Note that trump cards can be beaten only by the trump cards of higher rank.
     30 
     31 There were $n$ rounds played in the game, so the discard pile now contains $2n$ cards. You want to reconstruct the rounds played in the game, but the cards in the discard pile are shuffled. Find any possible sequence of $n$ rounds that might have been played in the game.
     32 
     33 Input
     34 
     35 The first line contains integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.
     36 
     37 The first line of a test case contains the integer number $n$ ($1\le n\le 16$).
     38 
     39 The second line of a test case contains one character, the trump suit. It is one of "CDHS".
     40 
     41 The third line of a test case contains the description of $2n$ cards. Each card is described by a two-character string, the first character is the rank of the card, which is one of "23456789", and the second one is the suit of the card, which is one of "CDHS". All cards are different.
     42 
     43 Output
     44 
     45 For each test case print the answer to it:
     46 
     47 * Print $n$ lines. In each line, print the description of two cards, in the same format as in the input: the first card that was played by the first player, and then the card that was used by the second player to beat it.
     48 * If there is no solution, print a single line "IMPOSSIBLE".
     49 
     50 If there are multiple solutions, print any of them.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 8
     58 
     59 3
     60 
     61 S
     62 
     63 3C 9S 4C 6D 3S 7S
     64 
     65 2
     66 
     67 C
     68 
     69 3S 5D 9S 6H
     70 
     71 1
     72 
     73 H
     74 
     75 6C 5D
     76 
     77 1
     78 
     79 S
     80 
     81 7S 3S
     82 
     83 1
     84 
     85 H
     86 
     87 9S 9H
     88 
     89 1
     90 
     91 S
     92 
     93 9S 9H
     94 
     95 1
     96 
     97 C
     98 
     99 9D 8H
    100 
    101 2
    102 
    103 C
    104 
    105 9C 9S 6H 8C
    106 ```
    107 
    108 Output
    109 
    110 ```
    111 3C 4C
    112 6D 9S
    113 3S 7S
    114 IMPOSSIBLE
    115 IMPOSSIBLE
    116 3S 7S
    117 9S 9H
    118 9H 9S
    119 IMPOSSIBLE
    120 6H 9C
    121 9S 8C
    122 ```