Problem
Mousetrap is a simple card game for one player. It is played with a
shuffled deck of cards numbered 1 through K, face down. You play by
revealing the top card of the deck and then putting it on the bottom
of the deck, keeping count of how many cards you have revealed. If you
reveal a card whose number matches the current count, remove it from
the deck and reset the count. If the count ever reaches K+1, you have
lost. If the deck runs out of cards, you win.
Suppose you have a deck of 5 cards, in the order 2, 5, 3, 1, 4. You
will reveal the 2 on count 1, the 5 on count 2, then the 3 on count 3.
Since the value matches the count, you remove the 3 from the deck, and
reset the count. You now have 4 cards left in the order 1, 4, 2, 5.
You then reveal the 1 on count 1, and remove it as well (you're doing
great so far!). Continuing in this way you will remove the 2, then the
4, and then finally the 5 for victory.
You would like to set up a deck of cards in such a way that you will
win the game and remove the cards in increasing order. We'll call a
deck organized in this way "perfect." For example, with 4 cards you
can organize the deck as 1, 4, 2, 3, and you will win by removing the
cards in the order 1, 2, 3, 4.
Input
The first line of input gives the number of cases, T. Each test case
starts with a line containing K, the number of cards in a deck. The
next line starts with an integer n, which is followed by n integers
(d1,d2, ...), indices into the deck.
Output
For each test case, output one line containing "Case #x: " followed by
n integers (k1,k2, ...), where ki is the value of the card at index di
of a perfect deck of size K. The numbers in the output should be
separated by spaces, and there must be at least one space following
the colon in each "Case #x:" line.
Limits
Small dataset
T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.
Large dataset
T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.
Sample
INPUT
2
5
5 1 2 3 4 5
15
4 3 4 7 10
OUTPUT
Case #1: 1 3 2 5 4
Case #2: 2 8 13 4
http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGJH6AQw#s=p2
The above is the 'cut-out' from the "MOUSETRAP" problem which appeared
in Google Code Jam 2008 ROUND 1B
I would request all of you to go through it first.
I could not understand the the difference between 'K' and 'n'
consequently test cases.(see the second input case 4 3 4 7 10, the
OUTPUT consists of 2 8 13 4 ) From where did these numbers come . im
confused . please help.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
