Tournament Construction
Contest: Codeforces Round 432 (Div. 1, based on IndiaHacks Final Round 2017)
Difficulty rating: 2800
Tags: constructive algorithms, dp, graphs, greedy, math

Ivan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges going outside this vertex.

Yesterday Ivan learned Landau's criterion: there is tournament with scores d1 ≤ d2 ≤ ... ≤ dn if and only if $$d_1 + \cdots + d_k \geqslant \frac{k(k-1)}{2}$$ for all 1 ≤ k < n and $$d_{1}+d_{2}+\cdots+d_{n}=\frac{n(n-1)}{2}$$.

Now, Ivan wanna solve following problem: given a set of numbers S = {a1, a2, ..., am}, is there a tournament with given set of scores? I.e. is there tournament with sequence of scores d1, d2, ..., dn such that if we remove duplicates in scores, we obtain the required set {a1, a2, ..., am}?

Find a tournament with minimum possible number of vertices.

Input format:
The first line contains a single integer m (1 ≤ m ≤ 31).

The next line contains m distinct integers a1, a2, ..., am (0 ≤ ai ≤ 30) — elements of the set S. It is guaranteed that all elements of the set are distinct.

Output format:
If there are no such tournaments, print string "=(" (without quotes).

Otherwise, print an integer n — the number of vertices in the tournament.

Then print n lines with n characters — matrix of the tournament. The j-th element in the i-th row should be 1 if the edge between the i-th and the j-th vertices is oriented towards the j-th vertex, and 0 otherwise. The main diagonal should contain only zeros.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2
1 2

Example output:
4
0011
1001
0100
0010

Example input:
2
0 3

Example output:
6
000111
100011
110001
011001
001101
000000

Editorial:
Let n be the number of players participating in the tournament. First of all, note that n ≤ 61, since the total number of wins must be $$\frac{n \times (n-1)}{2}$$, and there can be no more than 30 × n, therefore $${ \frac { n \times ( n - 1 ) } { 2 } } \leq 3 0 \times n$$, hence n ≤ 61. Next, we find an appropriate n, based on the criterion of the condition. We will go through all possible n from 1 to 61 and use the dynamic programming method to determine whether there can be a given number of participants, the parameters will be:
• the current element in the sorted list apos
• how many participants are already aware of their number of victories
• the total number of wins for the already known participants
From these parameters, we store whether it is possible for the remaining participants to assign any apos, apos + 1... am so that there is a tournament for these participants. Also, do not forget that each of ai should be taken at least once. Further, if we did not find n, then we print  - 1. Otherwise, you can recover from the dynamics how many times we took each ai, it remains to build a correct tournament on these values.
To do this, each time we take the player with the smallest number of wins, let this number be x, and we make him win x other players with the least number of wins, and loose to the remaining players. Next, delete this player, recompute for each remaining player how many times they have to win, and continue this process until all of the players are processed. The proof that a correct tournament is always built by this algorithm follows from the criterion.
Thus, the first part works in $${\mathcal{O}}(m^{5})$$ the second part works in $${ \mathcal { O } } ( m ^ { 2 } \times \log m )$$.