DWITE '12 R2 #4 - Magic Trick

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
DWITE, November 2012, Problem 4

Your friend is trying to convince you of his magical powers. He decides to perform the following trick to persuade you: Given a list of N shuffled cards, where each card has a unique number from \{1, 2, \dots, N\} written on it, he'll guess the numbers on the cards. Knowing that this is highly improbable, you call his bluff. He then continues to tell you that he still needs one more piece of information for this trick to work. For every card in the deck, he needs to know how many cards after this card has a bigger number written on it. Being a Computer Science student, you claim that you can write a program to do this simple trick as well.

The input will contain 5 test cases. Each test case consists of 2 lines. The first line will contain an integer 1 \le N \le 100, the number of cards in a deck. The following line will contain N numbers, separated by a space. Where each number represents the count of cards in the deck, with a larger value than the card in the position of that number. e.g. a list that starts with "1\ 3\ 2\ \dots" says that there is 1 card greater than the first in the deck, 3 cards greater than the second card in the deck, etc.

The output will contain 5 lines of output. Each a line of space separated numbers representing the original order of the deck in a corresponding test case. If no such deck can be constructed, print IMPOSSIBLE.

Sample Input

3
1 1 0
4
2 2 2 2

Sample Output

2 1 3
IMPOSSIBLE

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.