Polish version    English version  
  About Olympic -> Problems -> II OI 1994/1995


 News
 About Olympic
About contest
Problems
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Problems archive
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: KOD
Author: Krzysztof Diks
The Coding of Permutations

III stage contest  

Every permutation A = (a1, ..., an) of numbers 1, ..., n can be coded by a sequence B = (b1, ..., bn) in which bi equals the number of all aj such that (j < i & aj > ai), for i = 1, ..., n.

Example

The sequence B = (0, 0, 1, 0, 2, 0, 4) is the code of the permutation A = (1, 5, 2, 6, 4, 7, 3).

Task

Write a program that:
  • reads from the text file KOD.IN the length n and successive elements of the sequence B,
  • examines whether it is a code of some permutation of numbers 1, ..., n,
  • if so, it finds that permutation and writes it in the text file KOD.OUT,
  • otherwise it writes in the file KOD.OUT one word NIE ("no").

Input

  • In the first line of the text file KOD.IN there is a positive integer n <= 30000. It is the number of elements of the sequence B.
  • In each of the following n lines there is one nonnegative integer not greater than 30000. It is the successive element of the sequence B.

Output

The file KOD.OUT should contain:
  • in each of n consecutive lines - one element of the permutation A, whose code is the sequence B written in the file KOD.IN,
  • one word NIE, if the sequence B is not a code of any permutation.

Examples

For the file KOD.IN:
7
0
0
1
0
2
0
4
the file KOD.OUT should contain:
1
5
2
6
4
7
3

For the file KOD.IN:

4
0
2
0
0
the file KOD.OUT should contain:
NIE

Your program should look for the file KOD.IN in the current directory and create the file KOD.OUT also in the current directory. The source file containing the program written by you should be named KOD.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file KOD.EXE.




Print friendly version