Under construction

Still being built. Things may change

Hit or Miss

Time limit1sMemory limit128 MB

Summary
Simulate a multi-player solitaire card game and either report the last card each player discarded or declare the position unwinnable.
Level

Medium7 of 10

Topics
Simulation, Queue, Implementation, Game theory
Solved
No attempts yet

Problem

"Hit or Miss" (also known as "Frustration", "Harvest", "Roll-Call", "Talkative", and "Treize") is a very simple solitaire card game, played as follows. Take a standard deck of 52 cards — four copies each of the values 1 through 13 (suits do not matter in this game) — shuffle it, and count through the deck as 1,2,3,…1, 2, 3, \dots, restarting at 11 after 1313. Each time you count, look at the top card of the deck and do one of two things:

  • If the number you say equals the value of the top card, discard that card from the deck.
  • Otherwise, move the top card to the bottom of the deck.

You win if you eventually remove every card from the deck (which may take a very long time).

The game generalizes to two or more players. The first player begins with all 52 cards; every other player starts with no cards. Whenever a player would discard (matches) a card, instead of discarding it she passes it to the next player, who then plays the same game starting from count 11. The last player truly discards each matched card rather than passing it back to the first player.

All players who currently hold cards act in lockstep, repeating the following two-step cycle:

  1. Each such player says his or her current count value and checks the top card. If it does not match, the top card is moved to the bottom of that player's deck; if it matches, the card is passed to the next player (or discarded, if this is the last player).
  2. Every player except the first takes the card that was passed to them during step 1 (if any) and places it at the bottom of their deck.

The cycle repeats until either the game is won (the last player discards the final card) or an unwinnable position is reached. A player's count advances by 11 after each value is said, wrapping from 1313 back to 11. If a player runs out of cards, that player pauses and waits until a card is passed to them, then resumes counting from where they left off. For example, if a player passes their last card on a count of 77, they wait until they receive a card and resume with count 88 at the start of the next cycle.

Input

The first line contains a single positive integer nn: the number of games to process. Each of the next nn lines describes one game and contains 5353 integers. The first integer is the number of players, in the range 11 to 1010; the remaining 5252 integers are the initial deck listed from the top card to the bottom card. Every card value is in the range 11 to 1313.

Output

For each game, output one line. The line begins with Case x:, where xx is the game number starting from 11, followed by a single space and then one of the following. If the game can never be completed, output unwinnable. Otherwise, output the value of the last card discarded by each player (the last card that player removed from their own hand — passed onward, or truly discarded for the last player), in player order. All values on the line are separated by single spaces.

Examples1

  1. Example 1

    Input
    2
    4 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13
    4 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1
    
    Expected output
    Case 1: 13 13 13 13
    Case 2: unwinnable