← 返回题目列表

Codeforces · 850/D

D. 赛事建设

中文机器翻译题面 查看原题

Ivan 正在读一本关于锦标赛的书。他知道锦标赛是一个有向图,每对顶点之间只有一条有向边。顶点的分数是超出该顶点的边的数量。

昨天 Ivan 学习了 Landau 的标准:存在分数为 d1 ≤ d2 ≤ ... ≤ dn 的锦标赛当且仅当 $$d_1 + \cdots + d_k \geqslant \frac{k(k-1)}{2}$$ 对于所有 1 ≤ k < n 且$$d_{1}+d_{2}+\cdots+d_{n}=\frac{n(n-1)}{2}$$。

现在,Ivan 想解决以下问题:给定一组数字 S = {a1, a2, ..., am},是否存在具有给定分数集的锦标赛? IE。是否存在分数序列为 d1, d2, ..., dn 的锦标赛,这样如果我们删除分数中的重复项,我们就可以获得所需的集合 {a1, a2, ..., am}?

找到一个具有最少可能顶点数的锦标赛。

输入

第一行包含一个整数 m (1 ≤ m ≤ 31)。

下一行包含 m 个不同的整数 a1, a2, ..., am (0 ≤ ai ≤ 30) — 集合 S 的元素。保证集合的所有元素都是不同的。

输出

如果没有这样的锦标赛,则打印字符串“=(”(不带引号)。

否则,打印一个整数 n — 锦标赛中的顶点数。

然后打印 n 行和 n 个字符 — 锦标赛的矩阵。如果第 i 个和第 j 个顶点之间的边朝向第 j 个顶点,则第 i 行中的第 j 个元素应为 1,否则为 0。主对角线应仅包含零。

示例

输入 #1

2
1 2

输出 #1

4
0011
1001
0100
0010

输入 #2

2
0 3

输出 #2

6
000111
100011
110001
011001
001101
000000