← 返回题目列表

AtCoder · rco_contest_2019_qual_a

A. 游客X的旅行计划

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

問題文

热爱旅行的X,N 想要制定一个巡回旅行计划,每天访问1个城市,并最终回到最初的城市。

具体来说,第0天在出发城市住宿,从第1天开始, N 每一天从所在城市出发,移动到当天要访问的城市进行观光和住宿。
这里,N 第n天要访问的城市已经定为出发城市。

为了便于管理,X 给每个城市 0 〜 N - 1 编上了不重复的编号。
但是,访问的顺序还没有确定。

爱步行的X,希望城市之间能够步行移动。
此外,为了使日程管理更简单,他希望每天的移动距离方差较小,从而保持每天移动时间相对固定。

在这里,城市的位置、城市之间的移动距离以及移动距离的方差定义如下。

  • 番号 i 的城市坐标为 (x_{i},\ y_{i}) 所表示。也有可能多个城市存在于相同的坐标。
  • 城市间的移动距离以欧几里得距离定义。
  • 分散 \(\mathit{variance}\) 是、j 第\(j\)天的移动距离为 d_{j} ,移动距离的平均为 \(\mathit{average}\) 时, \[ \mathit{方差} = \frac{1}{N} \sum_{j=1}^{N}(d_j - \mathit{平均值})^2 \] 定义。


在收集城市观光信息时,请考虑访问城市的顺序,使移动距离的分散尽可能小,而不是每个忙碌的X。

每个thesutokeesu的得分和本题的得分计算如下。

  • 一个TESU的得分是向上取整至计算出的小数据点数的 \(10^6\div(1+\mathit{variance})\)。
  • 总共 50 确实有一些。 每个测试的总分即为该题目的总分。

入力

输入是按以下格式从标准输入给出的。

N
x_{0} y_{0}
\(\vdots\)
x_{i} y_{i}
\(\vdots\)
x_{N-1} y_{N-1}
  • N 是表示你计划访问城市数量的整数,N=200 感到满意。
  • x_{i},\ y_{i} 是一个数字 一对整数代表城市 i 的坐标, 0≤x_{i},\ y_{i}≤500 感到满意。

出力

i 行上, i 当天访问的城市数量 请输出 c_{i} 。 (c_{0} 是起始城市。 )
c_{N}=c_{0} ,所以 不输出 c_{N} 。

c_{0}
\(\vdots\)
c_{i}
\(\vdots\)
c_{N-1}

关于测试用例生成

每个城市的坐标是随机生成的。


入力例1

4
98 76
456 432
390 67
123 456

注意:此输入不满足作为测试用例的约束。

出力例1

0
2
1
3

行驶距离为 \(292.13\cdots, 370.91\cdots, 333.86\cdots, 380.82\cdots\),
平均行驶距离为 \(344.43\cdots\),方差为 \(1218.01\cdots\),得分为 \(821\)。

移动路径可视化结果如下所示。
短行进距离显示为红色,长行进距离显示为蓝色,接近平均值的行进距离显示为绿色。

生成器和测试器以及样本输入数据

测试用例生成器、测试器和示例输入数据由以下链接提供。

发电机测试仪样本输入数据


展示台

我们准备了一个可视化工具,可以可视化分数计算以及输入和输出文件的结果。

  • 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。特别是,已经确认它不能在 Internet Explorer 上运行。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台