← 返回题目列表

AtCoder · diverta2019_2_f

F. 迪维尔塔市

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

分数: 900 点

问题陈述

Diverta City 是一个新城市,由 N 城镇编号 1, 2, ..., N.

市长林戈计划用一条双向道路连接每对两个不同的城镇。每条路的长度尚未确定。

A 哈密顿路径 是一条从其中一个城镇开始并访问其他每个城镇一次的路径。 哈密​​顿路径的反转被认为与原始哈密顿路径相同。

有 N! / 2 哈密顿路径。林戈希望所有这些路径都有不同的总长度(一条路径上道路长度的总和),以使城市多样化。

在以下条件下找到一组这样的道路长度:

  • 每条道路的长度必须是正整数。
  • 哈密顿路径的最大总长度必须最多为 10^{11}.

约束

  • N 是介于 2 和 10 (含)。

输入

输入由标准输入按以下格式给出:

N

输出

按以下格式打印一组满足目标的道路长度:

w_{1, 1} \ w_{1, 2} \ w_{1, 3} \ ... \ w_{1, N}
w_{2, 1} \ w_{2, 2} \ w_{2, 3} \ ... \ w_{2, N}
  :  :     :
w_{N, 1} \ w_{N, 2} \ w_{N, 3} \ ... \ w_{N, N}

其中 w_{i, j} 是连接城镇的道路长度 i 和镇 j,必须满足以下条件:

  • w_{i, i} = 0
  • w_{i, j} = w_{j, i} \ (i \neq j)
  • 1 \leq w_{i, j} \leq 10^{11} \ (i \neq j)

如果存在多组满足目标的道路长度,则将接受其中任何一组。


示例输入 1

3

示例输出 1

0 6 15
6 0 21
15 21 0

存在三个哈密顿路径。这些路径的总长度如下:

  • 1 → 2 → 3:总长度为 6 + 21 = 27.
  • 1 → 3 → 2:总长度为 15 + 21 = 36.
  • 2 → 1 → 3:总长度为 6 + 15 = 21.

它们是不同的,因此达到了目标。


示例输入 2

4

示例输出 2

0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0

有 12 哈密顿路径,具有不同的总长度。