Wolf
Time limit2sMemory limit512 MB
Given your n-card pile and the opponent's remaining 51... wait 52-n cards, decide whether reordering both piles can make you win the next turn.
- Level
Hard8 of 10
- Topics
- Greedy, Sorting, Implementation, Brute force
- Solved
- No attempts yet
Problem
Wolf is a two player card game that grew out of War and Svälta räv. The two piles together form one standard deck. A deck has 52 cards, and each card is a distinct pairing of one of 4 suits with one of 13 ranks. The suits are clubs C, diamonds D, hearts H and spades S, and the ranks run from 1 to 13. An ace is written as 1, a jack as 11, a queen as 12 and a king as 13, and a smaller number means a lower rank.
A turn runs like this. Both players take the top card of their own pile at the same time and show it. If the two cards have different suits, each player takes another card and shows it, and this repeats until the two shown cards have the same suit. When the suits match, the player whose card has the higher rank takes every card shown so far and the turn ends. The turn also ends when a player has to take a card and their pile is empty. That player loses the game. If both piles are empty at the same moment, the game is a draw.
Your opponent is away from the table, so you may reorder both piles however you like. You cannot move a card from one pile to the other, because your opponent knows which cards their pile holds. Decide whether some ordering of the two piles wins the next turn for you. You win the turn by taking the shown cards after a matching suit, or by having a card left when the opponent's pile runs out.
Input
The first line contains the number of cards in your pile ().
Each of the next lines contains one card: a rank from 1 to 13 and one of the letters C, D, H, S, separated by a space. The cards are distinct, and the opponent holds the remaining cards of the deck.
Output
Print possible on the first line if some reordering of the two piles wins the next turn for you, and impossible if none does. Print either word in lowercase.