← 返回题目列表

AtCoder · rco_contest_2018_qual_b

B. 游戏解说X碎片整理

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

問題文

作为人气游戏实况者进行活动的X,正在整理拍摄积累的动画。
因为加载动画需要时间,调查后发现,似乎文件碎片化已经加重。

X拍摄积累的动画以特殊的文件存储方式,按照以下条件保存。

  • 一个动画文件保存在存储上的纵列 H 行、横 W 上排列的扇区中。
    • 左上角的扇区为 (0,\ 0)右下角的扇区为 (H - 1,\ W - 1) 。 在第
  • 文件由 D 个扇区分开保存,这些扇区的位置 (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) 。
  • 上述位置中未出现的扇区为空闲区,未保存任何内容。
  • 在读取文件时存在以下限制。
    • 要读取 feiru,需要按顺序访问构成该 fei 文件的扇区。 (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) 需要按照顺序访问。
    • 为了访问扇区,需要移动到位置 (a,\ b) 减去 (c,\ d) 要移动到 |c - a| + |d - b| 会产生成本。
    • feiru 的读取成本就是这些移动成本的总和。也就是说

X 决定通过重复交换来消除文件碎片(defrag),从而减少文件读取成本。
交换是指在纵列排列的扇区中 H 行、横 W 任意两个扇区(无论是否有数据)状态的互换操作。
不过,X 听说 defrag 会缩短存储器的消耗,所以将交换操作的次数限制为最多 K 次。

请替忙于游戏实际情况的X进行调试,并将文件读取成本最小化。

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

  • 在一个测试用例中, max(0,\ (青少年状态的成本 - 最终状态的成本)/100) 将小数点以下进一取整后得到分数。
  • 总共有 30 个。每个测试案例的分数总和将作为这个问题的得分。

入力

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

H W D K
r_{0} c_{0}
:
r_{D-1} c_{D-1}
  • H 是一个整数,表示扇区中的行数, 满足H = 200 满足。
  • W 是一个整数,表示扇区中的列数,W = 200 满足。
  • D 是一个整数,表示文件数据的扇区数,D = 16000 满足。
  • K 是一个整数,表示交换操作的最大次数,K = 4000 满足。
  • r_{i}\ c_{i} 是表示写入数据的扇区的位置的坐标,并且满足以下条件。
    • 0 ≤ r_{i} < H
    • 0 ≤ c_{i} < W
    • (r_{i},\ c_{i}) 都不同

出力

设置一对要交换的扇区位置,每行一个,最多 请输出到 K 行。
部门 如果你想替换 (a,\ b) 和 按字典顺序比较 (c,\ d) ,a\ b\ c\ d 。

a_{0} b_{0} c_{0} d_{0}
a_{1} b_{1} c_{1} d_{1}
:
  • 同一扇区的交换也是可能的。
  • 如果输出超过 K 行或交换超出范围,将显示 WA(错误答案)。

关于测试案例的生成

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


入力例1

5 5 5 4000
0 0
4 4
4 0
0 4
2 2

注意:这个输入不满足作为测试案例的条件。

该扇区的状态如下所示。

  

文件读取成本为 8 + 4 + 8 + 4 = 24。

出力例1

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

执行交换后输出的扇区状态如下。

  

读取文件的成本为 3 + 3 + 2 + 1 = 9。
本例中的分数为 max(0, (24 - 9)/100) = 0.15,四舍五入到最接近的整数。

发生器和测试仪

我们在以下链接提供测试用例生成器和测试器。

发电机测试仪


展示台

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

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

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

展示台

观察仪主体
fps
交换((
,
), (
,
))
将绘图内容保存为图像