← 返回题目列表

AtCoder · ahc014_a

A. 矩形连接

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

问题陈述

RectJoin 是以下使用方格纸和铅笔玩的单人游戏。

example

让 (0, 0) 为网格纸左下角的坐标, x- 轴向右且 y- 轴到顶部。 网格纸右上角的坐标为 (N-1, N-1)。 最初, M 在网格点上放置点,您可以尽可能多次地重复以下操作,以在网格纸上放置点并绘制矩形。

在 i第次操作,选择一个网格点 p_{i,1} 不包含一个点和三个网格点 p_{i,2}, p_{i,3}, p_{i,4} 包含满足以下三个条件的点。

  1. 正在连接 p_{i,1} p_{i,2} p_{i,3} p_{i,4} 以此顺序形成平行于轴线或倾斜45度的矩形。
  2. 除了 p_{i,2}, p_{i,3}, p_{i,4} 在此矩形的周边上。
  3. 该矩形的周长与已绘制的矩形的周长不共享正长度的公共线段(允许在某些点相交)。

对于所选的四个点,在 p_{i,1} 并绘制矩形的周长 p_{i,1} p_{i,2} p_{i,3} p_{i,4} 在网格纸上。

让 (c,c)=((N-1)/2,(N-1)/2) 是方格纸中心的坐标。 我们定义每个网格点的权重为 w(x,y)=(x-c)^2 + (y-c)^2 + 1 使用距中心的距离。 让 S=\sum_{x=0}^{N-1}\sum_{y=0}^{N-1} w(x,y) 是所有网格点的权重之和。 让 Q 是最终状态下点的坐标集(包括最初放置的点)。 然后你会得到以下分数。

\[\mathrm{round}\left(10^6 \cdot\frac{N^2}{M}\cdot\frac{\sum_{(x, y)\in Q} w(x, y)}{S}\right)\]

创建一个程序来玩游戏以获得尽可能高的分数。

规则补充说明

  • 您必须选择 p_{i,1} 从网格纸的内部,即从满足的坐标 0\leq x,y\leq N-1.
  • 由于一个点被放置在选择为的网格点上 p_{i,1},不能再次选择为 p_{j,1} in j(>i)-th 操作,但可以再次选择为 p_{j,k} (k=2,3,4).
  • 同样, p_{i,k} (k=2,3,4) 可以重复选择为 p_{j,k'} (k'=2,3,4) in j(>i)第次操作。
  • 如条件 2 中所述,所选矩形的周长上不能有其他点,但相反,您可以在已绘制的矩形的周长上选择一个点,如下所示 p_{i,1} 并在其上放置一个点。

测试用例数量

  • 临时测试:50
  • 系统测试:2000年。我们将发布 种子.txt (sha256=907b41fcba240515612a21798a10b0df7dda744b1268b74b3bbd41b93a73095e) 比赛结束后。
  • 系统测试包含 125 个输入,每个输入 N=31,33,35,\cdots,61.
  • seed=0的输入是手动创建的,不包含在临时或系统测试中。

提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 最终排名将由比赛结束后进行系统测试并进行更多投入来确定。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。 系统测试仅针对 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。


输入

输入由标准输入按以下格式给出:

N M
x_1 y_1
\vdots
x_M y_M
  • N 是31到61之间的奇数,代表网格纸上垂直和水平网格点的数量。
  • M 表示最初放置的点数,满足 N\leq M\leq \lfloor N^2/12 \rfloor.
  • (x_1, y_1), \cdots, (x_M, y_M) 表示坐标 M 点,每个点满足 \lfloor N/4\rfloor\leq x_i,y_i\leq\lfloor 3N/4\rfloor.

输出

让 K 是操作总数, (x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), (x_{i,3}, y_{i,3}), (x_{i,4}, y_{i,4}) 是在 i第次操作。 然后,按以下格式输出到标准输出。

K
x_{1,1} y_{1,1} x_{1,2} y_{1,2} x_{1,3} y_{1,3} x_{1,4} y_{1,4}
\vdots
x_{K,1} y_{K,1} x_{K,2} y_{K,2} x_{K,3} y_{K,3} x_{K,4} y_{K,4}

四个点的顺序可以是顺时针或逆时针,但是 (x_{i,1}, y_{i,1}) 必须是放置新点的点。

显示示例

输入生成

seed=0 的输入是手动创建的,不包含在临时或系统测试中。 让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

的一代 N 和 M

N=\mathrm{rand}(15, 30)\times 2 + 1, M=\mathrm{rand}(N, \lfloor N^2/12 \rfloor).

的一代 (x_i, y_i)

M 网格点 (x,y) 满意 \lfloor N/4\rfloor\leq x,y\leq\lfloor 3N/4\rfloor 是随机选择的。

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

比赛期间,您可以在 Twitter 上分享提供的 Seed=0 可视化工具的输出图像 (PNG)。 请注意,禁止以动画格式分享。 您必须使用指定的标签和公共帐户。 您只能共享seed=0 的可视化结果和分数。 请勿分享 GIF、输出本身、其他种子的分数或提及解决方案或讨论。

共享图像列表


示例输入 1

33 58
13 24
14 24
15 24
16 24
17 24
12 23
18 23
11 22
19 22
10 21
20 21
9 20
21 20
8 19
15 19
18 19
22 19
8 18
12 18
15 18
18 18
22 18
8 17
12 17
15 17
18 17
22 17
8 16
12 16
15 16
18 16
22 16
8 15
12 15
15 15
18 15
22 15
9 14
12 14
15 14
18 14
21 14
10 13
12 13
15 13
18 13
20 13
22 13
11 12
12 12
15 12
18 12
19 12
23 12
12 11
15 11
18 11
24 11

示例输出 1

20
9 15 12 12 15 15 12 18
15 20 12 17 15 14 18 17
23 22 19 22 19 12 23 12
23 14 22 15 21 14 22 13
10 14 10 13 12 13 12 14
11 11 12 11 12 12 11 12
18 20 15 20 15 19 18 19
19 16 22 19 21 20 18 17
12 19 12 18 15 18 15 19
15 22 12 19 15 16 18 19
14 22 15 22 15 24 14 24
15 8 18 11 15 14 12 11
10 15 9 15 9 14 10 14
11 18 12 19 10 21 9 20
22 23 20 21 21 20 23 22
21 15 18 15 18 14 21 14
15 26 13 24 15 22 17 24
20 20 16 24 14 22 18 18
21 17 18 20 15 17 18 14
11 14 10 13 11 12 12 13