问题陈述
AtCoder 正在开发一种教育玩具,它可以组合块来创建具有指定轮廓的三维对象。 该玩具由一组多边形块组成,其中包括 1\times 1\times 1 立方体面对面连接,并有一对两个 2D 单色剪影图像。 如果您可以通过组合块来构建单个 3D 对象,并且所创建对象的两个轮廓(从正面和右侧观看)与给定的轮廓图像完全匹配,您将赢得游戏。
为了让孩子们能够长时间玩耍,我们想为一组积木准备多对剪影。 例如,左图所示的 6 个块组可用于创建两对剪影,如右图所示。
作为一名玩具设计师,您会得到两对前/右轮廓,您的任务是找到一组块,您可以从中构建两个具有给定轮廓对的对象,以及构建它们的方法。 由于儿童可能会意外吞下小块,因此最好只由少量大块组成。
详细的拼图规则
- 你不必使用所有的块(但如果你这样做你会得到更好的分数)。
- 每个块可以绕 x 轴、y 轴和 z 轴旋转 90 度,但不能翻转。
- 块的排列必须使每个顶点都有整数坐标,并且不同的块不得具有正的公共体积。
- 构造的对象不必连接。为了简单起见,我们假设浮动排列也是可能的(您可以将其解释为存在大量额外的透明块,这些透明块可用于支撑块)。
关于剪影
从左到右取 x 轴,从前到后取 y 轴,从上到下取 z 轴。 我们假设所有块都在一个立方区域内,该区域具有 (0,0,0) 和 (D,D,D) 作为对角。 我们定义一个三维01数组 b(x,y,z) as b(x,y,z)=1 如果某个块占据了具有 (x,y,z) 和 (x+1,y+1,z+1) 作为对角,并且 b(x,y,z)=0 否则。 那么,从正面看的剪影就是一个二维的01数组 f(z,x) 定义如下。
\[ f(z,x)=\begin{情况} 1&(\sum_{y=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{y=0}^{D-1}b(x,y,z)=0) \结束{案例} \]
同样,从右侧看到的剪影是一个二维01数组 r(z,y),定义如下
\[ r(z,y)=\begin{情况} 1&(\sum_{x=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{x=0}^{D-1}b(x,y,z)=0) \结束{案例} \]
评分
让 v_1,\cdots,v_n 是所创建的玩具组中每个块的体积。 这里,块的体积等于块的数量 1\times 1\times 1 它包含立方体。 每个块必须是连接的,即它所包含的每个立方体都必须可以通过移动共享面来到达。 如果存在断开的块,则判断为 WA。 请注意,通过组合块创建的 3D 对象可以断开连接。
对于 i第一对剪影 (i=1,2),让 r_i 是输出 3D 对象中未使用的块的体积总和。 让 S 是两个对象中使用的块集。 然后就可以得到如下的评价值。 评价值越低越好。
\[ \mathrm{round}\left(10^9\times \left(r_1+r_2+\sum_{i\in S} \frac{1}{v_i}\right)\right) \]
例如,如果该组块由体积为 5 的块 A、体积为 3 的块 B 和体积为 2 的块 C 组成,并且如果第一组轮廓由可使用 A 和 B 创建的 3D 对象实现,第二组轮廓由可使用 A 和 C 创建的 3D 对象实现,则所得评估值为 \mathrm{round}\left(10^9\times \left(2+3+1/5\right)\right).
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的评估值,MIN 是在该测试用例中获得的所有竞争对手中的最低评估值。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=08db725cbdc37734a2e8fbe5bc0cbc1e95d7a68933b7f43dcdd0ffc3d2a95e34) 比赛结束后。
- 系统测试包含 200 每个的输入 D=5,6,\cdots,14,其中 D 是每个轮廓的尺寸。
- 种子 = 0 的输入是手动创建的,不包含在临时或系统测试中。
关于相关评价体系
在临时/系统测试中,将仅使用收到除以下结果之外的最后提交的结果来计算排名 CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的评估值的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出:
D f_1(0,0) \cdots f_1(0,D-1) \vdots f_1(D-1,0) \cdots f_1(D-1,D-1) r_1(0,0) \cdots r_1(0,D-1) \vdots r_1(D-1,0) \cdots r_1(D-1,D-1) f_2(0,0) \cdots f_2(0,D-1) \vdots f_2(D-1,0) \cdots f_2(D-1,D-1) r_2(0,0) \cdots r_2(0,D-1) \vdots r_2(D-1,0) \cdots r_2(D-1,D-1)
- D 是剪影图像的尺寸并且满足 5\leq D\leq 14.
- f_i,r_i 是 i-第对轮廓图像,其中 f_i 是从正面看的剪影, r_i 是从右侧看到的剪影。每个都是01大小的矩阵 D\times D 给出为 D 01 字符串长度 D。这些值的含义请参见上一节“关于轮廓”。
- 对于每个轮廓,所有 1 个元素形成一个连通分量。
- 对于 z=0,\cdots,D-1,它认为 f_i(z,0)+\cdots+f_i(z,D-1)\geq 1 和 r_i(z,0)+\cdots+r_i(z,D-1)\geq 1。此条件保证始终存在与指定的轮廓对匹配的 3D 对象。
输出
让 n 是块的总数。 对应的块排列 i第对剪影使用三维数组表示如下 b_i(x,y,z) 尺寸 D\times D\times D.
b_i(x,y,z)=k 如果 k (1\leq k\leq n)-th 块占据具有 (x,y,z) 和 (x+1,y+1,z+1) 作为对角,并且 b(x,y,z)=0 如果没有任何块占据该区域。
由于块无法重新整形,因此两个块中都会出现相同编号的块 i=1,2 必须具有相同的形状,即它们必须能够通过旋转和平移完美匹配。
然后,按以下格式输出到标准输出。
n b_1(0,0,0) b_1(0,0,1) \cdots b_1(D-1,D-1,D-1) b_2(0,0,0) b_2(0,0,1) \cdots b_2(D-1,D-1,D-1)
在这里, (x\times D^2+y\times D+z)- 第一个输出 b_i is b_i(x,y,z)。 对于每个 i=1,\cdots,n, i-th 块必须至少用于以下之一: b_1 or b_2。如果有一个块没有被使用,则判断为 WA.
示例解决方案
D = int(input())
f = [[] for i in range(2)]
r = [[] for i in range(2)]
for i in range(2):
for k in range(D):
f[i].append(input())
for k in range(D):
r[i].append(input())
b = [[0 for j in range(D * D * D)] for i in range(2)]
n = 0
for i in range(2):
for x in range(D):
for y in range(D):
for z in range(D):
if f[i][z][x] == '1' and r[i][z][y] == '1':
n += 1
b[i][x * D * D + y * D + z] = n
print(n)
print(' '.join(map(str, b[0])))
print(' '.join(map(str, b[1])))
输入生成
的一代 D
我们生成 D by D=\mathrm{randint}(5,14).
的一代 f,r
首先,我们生成以下值,这些值确定要生成的轮廓的特征。
- p(0)=0
- p(1)=D^{\mathrm{randdouble}(-1,1)}
- p(2)=D^{\mathrm{randdouble}(-1,1)}
- p(3)=D^{\mathrm{randdouble}(-0.5,1.5)}
- p(4)=D^{\mathrm{randdouble}(-0.5,1.5)}
接下来,我们生成每个 f_1,r_1,f_2,r_2 如下。
让 g 是要生成的轮廓数组并用以下命令对其进行初始化 g(z,x)=0 对于所有人 (z,x)。 生成一个值 m=\mathrm{randint}(2D,\lfloor D^2/2\rfloor) 代表数量 1。 生成 z=\mathrm{randint}(0,D-1) 和 x=\mathrm{randint}(0,D-1),然后设置 g(z,x)=1。 重复以下过程,直到达到 1 变为 m.
对于每个 (z,x),让 d(z,x) 是相邻的数量 1 在四个方向。 选择 (z,x) 这样 g(z,x)=0 概率与 p(d(z,x)) 并更新 g(z,x)=1.
当数量 1 变为 m,检查是否 \sum_{x=0}^{D-1}g(z,x)\geq 1 对于所有人 z=0,\cdots,D-1,如果没有,则重新初始化 g to 0 并重试生成过程 m.
工具(输入生成器和可视化工具)
- 网页版:您可以看到 3D 动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
比赛期间,您可以在 Twitter 上分享提供的 Seed=0 可视化工具的输出图像 (PNG)。 您必须使用指定的标签和公共帐户。您只能共享seed=0 的可视化结果和分数。请勿分享视频、输出本身、其他种子的分数或提及解决方案或讨论。
示例输入 1
5 10001 11011 11111 10101 10001 01110 11011 10000 11011 01110 11110 00011 01110 11000 11111 11110 00011 01110 00011 11110
示例输出 1
19 0 1 2 3 0 4 5 0 3 3 6 0 0 0 3 7 7 0 3 3 0 7 0 8 0 0 5 9 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 9 10 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 12 12 0 13 0 0 12 14 0 0 0 0 14 0 0 0 14 14 0 0 0 14 0 15 0 0 0 3 14 0 0 0 3 0 0 0 0 9 16 0 0 9 9 0 0 0 17 0 0 0 0 0 0 14 0 10 0 3 14 0 10 0 9 0 0 0 18 0 0 0 0 0 0 0 0 0 0 3 0 0 12 0 3 14 0 12 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 12 0 0 14 0 7 0 0 0 7 7 0 5 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 7 0 0 5 0 0 0 0 0