DWITE
November 2012
Problem 4
Magic Trick

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, ..., 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 of 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 file DATA4.txt will contain 5 test cases. Each test case consists of 2 lines. The first line will contain an integer 1 <= N <= 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 ..." 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 file OUT4.txt 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 (first 2 shown):
 
3
1 1 0
4
2 2 2 2
		        
Sample Output (first 2 shown):
 
2 1 3
IMPOSSIBLE
		        

Notes: for the first case, going backwards from the solution: the first card has value 2, and there is only 1 card with greater value after it (3). Second card has value 1, and there is only 1 card with greater value after it (3). The last card has value of 3, and there are no cards with greater value. So the input of "1 1 0" checks out.

The second case is IMPOSSIBLE, most obviously because it expects 2 cards with greater value than the last card, but there are no more cards to match this requirement.