← 返回题目列表

AtCoder · ahc062_a

A. 国王之旅

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

故事

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}.

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。