• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Sign in to follow this  
Followers 0

Mousetrap - Treino ONI

2 posts in this topic

Isto anda um pouco parado, por isso aqui vai um exercício (Google Codejam 2008) que penso ser de nível de ONI.

Título: Mousetrap


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.


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.


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.


Para 30% do pontos (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



5 1 2 3 4 5


4 3 4 7 10

Sample Output

Case #1: 1 3 2 5 4

Case #2: 2 8 13 4


O programa tem 4 minutos para responder ao Small dataset e 8 minutos para responder ao large dataset. No entanto, isto é para dar uma folga grande. O meu programa é instantâneo no small dataset e demora 12 segundos no large dataset (numas ONI, provavelmente só haveria um caso de teste por ficheiro).


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
Followers 0