← 返回题目列表

Codeforces · 42/D

D. 陌生的小镇

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

Volodya 最近访问了一个非常奇怪的城镇。镇内有N个旅游景点,每两个景点有一条双向路连接。每条道路都有一些分配给它的旅行价格(自然数),并且所有价格都是不同的。但这个小镇最引人注目的是,每个城市观光旅游的总价都是一样的!也就是说,如果我们选择任何城市观光旅游——每个景点都参观一次的循环——旅游道路的成本总和与旅游无关。 Volodya 很好奇是否能找到这样的价格体系,所有公路价格不大于 1000。

输入

输入仅包含一个自然数 (3 ≤ N ≤ 20) — 城镇景点的数量。

输出

输出应包含 N 行,每行包含 N 个正整数 — 价格图的邻接矩阵(因此,第 i 行中的第 j 个数字应等于第 j 个景点和第 i 个景点之间的道路价格)。对角线数应等于零。所有数字不得大于 1000。所有价格均应为正且两两不同。如果有多个解,输出任意一个。

示例

输入 #1

3

输出 #1

0 3 4
3 0 5
4 5 0