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: DRZ
Author: Wojciech Rytter
Trees

I stage contest  

Trees occur very often in computer science. As opposed to trees in nature, computer science trees "grow upside down"; the root is up and the leaves are down.

A tree consists of elements named nodes. A root is one of the nodes. Each node w (except for the root) has its (exactly one) father v. If the node v is the father of w, then w is a son of v. Nodes that have no sons are called leaves. Sons of the node w, their sons, sons of their sons, and so on, are called descendants of the node w. Every node - except for the root - is a descendant of the root.

Each node has a level number assigned to it. The level number of the root is 0, and the level number of sons is greater by 1 then that of their father.

A tree is a complete binary tree if and only if each node has exactly two or zero sons. In binary trees sons are named left and right.

The following picture shows an example of a complete binary tree. The nodes of that tree are numbered in a special order called preorder. In this order the root has the number 1, a father precedes its sons, and the left son and any its descendant have smaller numbers than the right son and every its descendant.

a preorder tree

There are many written representations of complete binary trees having such numbering of nodes. Three ones follow.

Genealogical representation. It is a sequence of numbers. The first element of the sequence equals 0 (zero), and for j > 1, the j-th element of the sequence is the number of the father of the node j.

Bracket representation. Each node corresponds to a string composed of brackets. Leaves correspond to "()". Each other node w corresponds to a string "(l r)", where l and r denote the strings that left and right sons of w respectively correspond to. The string the root corresponds to is the bracket representation of the tree.

Level representation. It is a sequence of level numbers of successive tree leaves (according to the assumed numbering).

The tree in the picture may be described as follows:
Genealogical representation  0 1 2 2 4 4 1 7 7
Bracket representation ((()(()()))(()()))
Level representation 2 3 3 2 2

Task

Write a program that reads from the text file DRZ.IN a sequence of numbers and examines whether it is the level representation of a complete binary tree. If not, the program writes one word NIE ("no") in the text file DRZ.OUT. If so, the program finds two other representations of this tree (genealogical and bracket ones), and writes them in the text file DRZ.OUT.

Input

In the first line of the file DRZ.IN there is a positive number of the sequence elements (not greater than 2500). In the second line there are successive elements of the sequence separated by single spaces.

The numbers in the file DRZ.IN are written correctly. Your program need not verify that.

Output

The file DRZ.OUT should contain:
  • either only one word NIE,
  • or in the first line - the consecutive elements of the genealogical representation, separated by single spaces;
    in the second line - the bracket representation, i.e. a sequence of left and right brackets with no spaces between them.

Examples

For the file DRZ.IN:
5
2 2 3 3 2
your program should create the following file DRZ.OUT:
0 1 2 2 1 5 6 6 5
((()())((()())()))
For the file DRZ.IN:
4
1 2 2 3
your program should create the file DRZ.OUT:
NIE

Your program should look for the file DRZ.IN in the current directory and create the file DRZ.OUT also in the current directory. The source file containing the program written by you should be named DRZ.???, 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 DRZ.EXE.




Print friendly version