4th Balkan Olympiad in Informatics
Nicosia, Cyprus, 19-25 October 1997

Day 2 - Problem 2 (Satellite configuration)



We want to launch a set of satellites in the sky in orbit around earth. Two satellites may transmit data to each other in a direct way, or in indirect way (i.e. via one or more intermediate satellites), or finally may have no connection at all. We say that two satellites are neighbors if they can send data to each other in a direct way.

Given a number n of satellites and a set of n integers, find out:

  1. if there exists a configuration of n satellites such that the given set of n integers correspond to the neighbors of the satellites
  2. if the answer in part (a) is positive, then describe such a setting,
  3. given the setting of part (b), conclude if we can send data from any satellite to any other one.




Input:
The input file INPUT.TXT consists of a line containing a sequence of integers separated by spaces. The first integer, a number n <= 20, gives the number of satellites in orbit. The following n integers represent the required number of neighbors for each one of the satellites. Note that the order of these n numbers (which represent the number of neighbors for each satellite) is not important.

Output:
The first line of the output file OUTPUT.TXT contains the answer to part (a): a YES or a NO. In case of a NO in part (a), then no more output is required. In case of a YES in part (a), then a number of n lines follow containing n integers 1 or 0 separated by spaces, forming an nxn matrix. If the (i,j)-th element of this matrix is 1, then the satellites i and j are neighbors, whereas if this element is 0 then these satellites are not neighbors. The (n+2)-th line of the output file corresponds to part (c) and is a YES or a NO.

Example 1:
  • Input:
    6 4 3 1 4 2 0
  • Output:
    NO

Example 2:
  • Input:
    7 4 3 1 5 4 2 1
  • Output:
    YES
    0 1 1 1 1 1 0
    1 0 1 0 0 0 0
    1 1 0 1 0 1 0
    1 0 1 0 0 1 0
    1 0 0 0 0 0 0
    1 0 1 1 0 0 1
    0 0 0 0 0 1 0
    YES


Example 3:
  • Input:
    6 2 3 1 1 2 1
  • Output:
    YES
    0 1 0 1 0 0
    1 0 1 1 0 0
    0 1 0 0 0 0
    1 1 0 0 0 0
    0 0 0 0 0 1
    0 0 0 0 1 0
    NO




Time Limit : 20
Maximum Score : 35