故事
AtCoder 王国分为 N \times N 区域网格,每个区域有不同数量的公民。 为了提高在国民中的知名度,高桥国王计划进行一次巡游,通过垂直、水平或对角相邻的地区来访问所有地区。 随着巡演变得越来越精彩,日后访问的地区居民对高桥的好感度也越来越高。 请计划一次旅行,以便高桥获得的总好感尽可能多。
问题陈述
有一个王国分为 N \times N 区域网格。设左上角的区域为 (0,0),并让移动到达的区域 i 地区向下和 j 右侧的地区是 (i,j)。 区 (i,j) 有 A_{i,j} 公民。
考虑一次将每个地区都参观一遍的旅行 N^2 天,从那天起 0 到今天 N^2-1。 让当天参观的地区 k be (i_k, j_k).
连续两天访问的地区必须是相邻的 垂直、水平或对角线。 更准确地说,对于每个 k=0,1,\dots,N^2-2,
\[ \max\bigl(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|\bigr)=1 \]
必须保留。 游览的起始地区和结束地区可以任意选择。
对于当天访问的地区 k 旅行中,每位居民都做出了贡献 k 赞成。 高桥获得的总好感度为
\[ \sum_{k=0}^{N^2-1} k\cdot A_{i_k, j_k} \]
找到一个访问顺序,使高桥获得的总好感尽可能大。
评分
让 V 是高桥获得的总好感。 那么该测试用例的分数是
\[ \mathrm{round}\left(\frac{V}{N^2}\right) \]
有 100 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
N
A_{0,0} \cdots A_{0,N-1}
\vdots
A_{N-1,0} \cdots A_{N-1,N-1}
- 在所有测试用例中, N=200.
- A_{i,j}, 地区公民数量 (i,j),是满足以下条件的整数 1\leq A_{i,j}\leq N^2.
输出
让 (i_k, j_k) 是当天访问的地区 k 的游览。按以下格式输出到标准输出。
i_0 j_0
\vdots
i_{N^2-1} j_{N^2-1}
您的输出必须满足以下所有条件。
- 对于 k=0,1,\cdots,N^2-1, i_k 和 j_k 是介于 0 和 N-1,包括在内。
- 全部 (i_k, j_k) 为 k=0,1,\cdots,N^2-1 是不同的。
- 对于 k=0,1,\cdots,N^2-2, \max(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|)=1 成立。
输入生成
- 在所有测试用例中, N=200.
- 的整数 1 to N^2 被随机均匀地洗牌,并按顺序分配 A_{0,0}, A_{0,1}, \cdots, A_{0,N-1}, A_{1,0}, \cdots, A_{N-1,N-1}.
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。