← 返回题目列表

AtCoder · toyota2023summer_final_a

A. 中转仓库

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

故事

高桥管理着一个用于运输集装箱的中转仓库。今天,许多集装箱计划运入这个仓库,而明天,所有这些集装箱将按预定顺序装上卡车进行运输。集装箱的到达顺序未知,因此请根据它们的装运顺序灵活地将它们存放在仓库中的适当位置。 被运出。

问题陈述

有一个仓库,其内部为网格状 D\times D 方块。 让 (0,0) 是最西北方格子的坐标,且 (i,j) 是位于以下位置格子的坐标 i 向南方的格子数,且 j 向东方的格子数。 仓库入口在格子 (0,(D-1)/2),其中 D 是一个奇数。 在以下位置有不可通行的障碍物 N 格子之外 D^2-4 方格,除了入口及其 3 相邻的方格。

D^2-1-N 容器一个接一个地被运入仓库。每个容器都被分配一个唯一的编号 0 to D^2-2-N ,该编号表示容器运出的顺序。 容器顺序的信息事先不可得,容器被运入时才会显示分配的编号。 每个 D\times D-1-N 方格除了入口和障碍物最多可以放置 1 个容器。每次引入一个容器时,选择一个方格来存放它。选定的方格必须满足以下条件:

  1. 它既不是入口也不是障碍物,并且选定的方格上没有存放其他容器。
  2. 它必须可以从入口到达,并且只能通过四个方向上相邻的空方格。

在所有容器存放完毕后,请逐一将它们运出。 要运出的容器必须满足以下条件。

  1. 要运输出的容器所在的方格必须可以从入口到达,并且仅能通过上下左右相邻的空方格通行。

优化容器的存放位置以及运输顺序,使得实际运输顺序尽可能接近指定顺序。

评分

让 b_i (0\leq b_i\leq D^2-2-N) 是分配给第 i次运输出的容器的编号(0\leq i\leq D^2-2-N)。 让 B 是 的倒演次数 b_0,\cdots,b_{D^2-2-N},即对数总数 (i,j) 这样 i < j 和 b_i>b_j。 然后,您将获得以下分数。

\[ \mathrm{round}\left(10^9\times \frac{(D^2-N)(D^2-1-N)/2-B}{(D^2-N)(D^2-1-N)/2}\right) \]

有 30 每个测试用例 N=0,1,\cdots,9,总计300个测试用例,提交的分数即为每个测试用例的总分。 如果你的提交产生了非法输出或超过某些测试用例的时间限制,提交本身将被评为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。

输入和输出

首先,仓库的大小, D障碍物的数量 N,以及障碍物的坐标 (ri_0,rj_0),\cdots,(ri_{N-1},rj_{N-1}) 将以以下格式从标准输入中给出。

D N
ri_0 rj_0
\vdots
ri_{N-1} rj_{N-1}

对于所有测试用例,我们修复 D = 9。 障碍物的数量 N 满足 0\leq N\leq D。 每个障碍物的坐标 (ri_k,rj_k) 与入口及其三个相邻的方格不同,此外,除障碍物外,所有方格都保证可以从入口到达。

阅读以上信息后,重复以下过程 D^2-1-N 次。

在 d第一个进程(0\leq d\leq D^2-2-N), 该数字 t_d 分配给 d-号集装箱从标准输入的一行中给出。 每个 t_d 是介于 0 和 D^2-2-N,并且每个集装箱都有一个唯一编号。

读取完 t_d的信息后,输出坐标 (pi_d,pj_d) 的平方,将容器存储到标准输出中,格式为单行如下。

pi_d pj_d

输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交内容可能会被判定为 TLE. 注意输入为 d+1-号集装箱将在给出第 d-次输出后才会提供。

在所有集装箱存放完毕后,确定集装箱的运输顺序。 让 (qi_k, qj_k) 是坐标 k-待运输出的容器。然后,按以下格式输出到标准输出。

qi_0 qj_0
qi_1 qj_1
\vdots
qi_{D^2-2-N} qj_{D^2-2-N}

您的程序可能会输出以#开头的注释行。网页版可视化工具会在相应的时间显示注释行,这可能有助于调试和分析。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。

例

d 输入 输出
先前信息
9 0
0
16
8 0
1
13
8 8
\vdots
79
34
0 5
运输订单
0 3
0 5
0 2
\vdots
8 8

显示示例

输入生成

障碍物数量 N 从以下整数中均匀随机生成 0 和 D,包含端点。 N 障碍物的不同坐标从除入口及其三个相邻方格外的方格中随机选择。 这些数字 t_0,\cdots,t_{D^2-2-N} 分配给容器是通过随机打乱生成的 0,1,\cdots,D^2-2-N.

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

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