← 返回题目列表

AtCoder · rco_contest_2018_final_a

A. 古古古花园

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

問題文

妖精研究员X花了很多年的时间来研究出现在某个花园里的彩虹色妖精。
众所周知,仙女有一种习惯,每天晚上出现在花园的一个地方,然后以最短路线飞到另一个地方,然后消失在那里。
经过多年的研究,X已经能够完美预测妖精的外貌模式,现在他想尽可能长时间地观察妖精。
具体来说,我们试图通过在花园中建造和摧毁墙壁来操纵仙女的移动路线来尽可能提高满意度。
然而,由于他每天只能建造或摧毁一堵墙,X 正在努力想出一个好的工作计划。

X试图执行的仙女观察具有以下条件。

  • 仙女出现的花园是 它由一个 N × N 网格组成,其中网格中的每个单元格要么是空的,要么是墙。
    • 从上面 r 行,从左 c 列单元格 表示为 (r,\ c) 。 ( 0 ≤ r,\ c < N )
  • 在初始状态下,所有单元格都是空的。另外,满意度为 0 。
  • 仙女观察是 K 按以下顺序计算每天的工作和满意度。
    1. 选择任意单元格,如果是空的,则将其更改为墙,如果是墙,则将其更改为空。或者什么也不做。细胞状态会延续到第二天。
    2. 妖精出现的牢房 细胞从 (a_{i},\ b_{i}) 中消失 (c_{i},\ d_{i}) 如果有一条路线,仙女只需沿着空单元格向上、下、左、右一次即可到达,那么最短路线是 (通过的细胞数,包括出现和消失的细胞 添加\ -\ 1)^2 作为满意度。
      • 如果达不到,仙女就不会出现,满意度也不会改变。 如果
      • (a_{i},\ b_{i}) 和 按字典顺序比较 (c_{i},\ d_{i}) 中至少有一个是墙,仙女就不会出现,满意度也不会改变。
      • 仙女无法穿过网格之外。

然而,X虽然擅长研究妖精,但却不擅长计算,所以他不知道该制定什么样的工作计划。
作为 X 值得信赖的朋友,您应该代表 X 制定工作计划,以最大限度地提高满意度。

每个测试用例和该问题的分数计算如下:

  • 在一个测试用例中,(最后一天的满意度/10000) 小数点以下舍入后的整数就是得分。
  • 一共有 50 个。各个测试用例的得分总和,就是这个问题的得分。

入力

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

N K
a_{0} b_{0} c_{0} d_{0}
:
a_{K-1} b_{K-1} c_{K-1} d_{K-1}
  • N 是一个整数,表示网格一侧的长度, 满足N = 40 满足。
  • K 是一个整数,表示观察仙女的天数,K = 1000 满足。
  • (a_{i},\ b_{i}),\ (c_{i},\ d_{i}) 是个仙女 i 表示在几天内出现和消失的细胞。
    • 0 ≤ a_{i},\ b_{i},\ c_{i},\ d_{i} < N
    • (a_{i},\ b_{i}) ≠ (c_{i},\ d_{i})

出力

每天工作的单元格坐标 (y,\ x) ,以空格分隔,一次一行,总计 K 行。 列出
如果您不想处理任何单元格, -1 -1 。

y_{0} x_{0}
:
y_{K-1} x_{K-1}
  • 输出是 如果未显示 K 行或者有网格范围之外的坐标,则会显示WA(错误答案)。

关于测试用例的生成

每个用例均由测试用例生成器生成。
测试用例生成器根据均匀随机数生成用例。
测试用例生成器可从页面底部的链接获取。


入力例1

5 4
0 1 4 4
2 2 2 3
0 4 4 0
0 0 4 0

注意:此输入未满足作为测试用例的否定条件。

出力例1

3 0
-1 -1
4 1
4 1

每天根据输出操作的花园状态和仙女飞行路径如下。

  

第二天,你无法从仙女消失的方格到达仙女出现的方格,所以仙女不会出现,满意度也不会改变。
该测试用例的分数是最后一天的满意度。 该值除以 86 该值应乘以 10000 并向上舍入。 1 。
(图中的S和G分别代表仙女出现和消失的单元格)

发生器和测试仪

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

发电机测试仪


展示台

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

  • 此可视化工具已经过测试,可在主要浏览器上运行,但不能保证在所有环境中都能运行。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

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

展示台

观察仪主体
fps
距離
距離2
将绘图内容保存为图像