UOJ Logo Universal Online Judge

UOJ

附件下载 统计

W 王国中有 $n$ 个城市,快递公司会在任意两个不同的城市之间配送快递。作为快递公司的总管理员,你打算把公司分成若干个部门并让这些部门之间相互竞争,以此来提高配送快递的效率。

划分部门并不是一件容易事,它需要考虑很多因素。对于两个不同的城市 $i,j$,如果 $i \to j$ 和 $j \to i$ 是由两个不同的部门负责的,那么一个部门配送完快递后返程就会没有事做,这样会浪费时间。对于三个不同的城市 $i,j,k$,如果 $i,j,k$ 之间六种配送方式都是由同一个部门负责的,那么你会觉着这个部门垄断了这三个城市之间的快递运输,这样对整个公司是不利的。因此,你规定:

  • 对于两个不同的城市 $i,j$,$i \to j$ 和 $j \to i$ 必须由同一个部门负责。
  • 对于三个不同的城市 $i,j,k$,它们之间六种配送关系不能由同一个部门负责。

由于划分出的部门数目太多会不利于公司的管理,所以你需要求出划分出的最少部门数目 $m$。

输入格式

一行一个整数 $n$。

输出格式

你需要用方案来证明你的答案,所以本题你需要输出方案。

你需要输出 $n$ 行,每行 $n$ 个整数,第 $i$ 行第 $j$ 列的整数 $A_{i,j}$ 表示第 $i$ 个城市和第 $j$ 个城市之间的快递运输由第 $A_{i,j}$ 个部门负责。

形式化地,假设你求出的最少划分数目为 $m$,那么你输出的矩阵 $A$ 需要满足以下性质:

  • 对于 $\forall i,j$ 且 $i\neq j$, 都有 $1\le A_{i,j} \le m$ 并且 $A_{i,j}$ 为整数。
  • 对于 $\forall i,j$, 都有 $A_{i,j}=A_{j,i}$。
  • 对于 $\forall i$, 都有 $A_{i,i}=0$。
  • 对于 $\forall i,j,k,i < j < k$,都有 $A_{i,j} \ ,A_{i,k} \ ,A_{j,k}$ 不完全相同。

你并不需要输出 $m$,在判断答案时会自动将你输出的数中的最大值作为 $m$。

样例一

input

3

output

0 1 2
1 0 1
2 1 0

限制与约定

本题是一道传统题,但表格中的限制为 $n=$ 并非 $n\le$。

如果你输出的方案不合法,那么该测试点得 $0$ 分。

如果你输出的方案所对应 $m$ 不是最少的划分数,那么该测试点得 $0$ 分。

否则,每个测试点的信息如下:

测试点编号 1 2 3 4 5 6 7 8 9 10
$n=$ 5 8 16 25 32 33 34 80 82 85
分值 5 5 10 10 5 10 20 5 10 20

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载