问题说明

$AtCoder$正在开发一种教育玩具，它将积木组合起来，创造出一个具有特定轮廓的三维物体。该玩具包括一套由$1×1×1$立方体面对面连接而成的多立方体积木和一对二维单色剪影图像。如果你能通过组合积木构建一个单一的三维物体，使创建的物体的两个剪影，从正面和右侧看，与给定的剪影图像完全一致，你将赢得游戏。

为了让孩子们玩得更久，我们要为一组积木准备多对剪影。例如，左图所示的一套6块积木，可以用来制作两对剪影，如右图所示。

作为一名玩具设计师，你得到了两对正面/右面的剪影，你的任务是找到一套积木，从这套积木中可以构造出具有给定的几对剪影的两个物体，并找到构造它们的方法。因为孩子们可能会不小心吞下小积木，所以一套积木最好只由少量的大积木组成。

详细的谜题规则

你不需要使用所有的积木（但是如果你使用了，你会得到一个更好的分数）。 每个积木都可以围绕$X$轴、$Y$轴和$Z$轴旋转$90$度，但不能翻转。 块的排列必须使每个顶点都有整数坐标，而且不同的块不能有正的共同体积。 构建的物体不一定要连接。为了简单起见，我们假设浮动排列也是可能的（你可以理解为有大量的额外透明块，可以用来支持块）。

关于剪影

从左到右取$X$轴，从前到后取$Y$轴，从上到下取$Z$轴。我们假设所有的区块都在一个立方体区域内，该区域的对角线为$（0,0,0）和（D,D,D）$。我们将三维01阵列$b(x,y,z)$定义为：如果某个区块占据了以$(x,y,z)$和$(x+1,y+1,z+1)$为对角线的立体区域，则$b(x,y,z)=1$，否则$b(x,y,z)=0$。那么，从正面看剪影是一个二维$01$阵列$f(z,x)$，定义如下。

$ f(z,x)=\begin{cases} 1&(\sum_{y=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{y=0}^{D-1}b(x,y,z)=0) \end{cases} $

同样，从右边看的剪影是一个二维$01$阵列$r(z,y)$，定义如下

$ r(z,y)=\begin{cases} 1&(\sum_{x=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{x=0}^{D-1}b(x,y,z)=0) \end{cases} $

得分

让$v 1, ⋯, v n$ 是创建的玩具组中每个块的体积。这里，一个积木的体积等于它所包含的$1×1×1$的立方体的数量。每个区块必须是相连的，即它所包含的每个立方体必须可以通过共享面的移动而到达。如果有一个断开连接的块，它将被判定为$WA$。请注意，通过组合块创建的三维物体可以是断开连接的。 对于第$i$对剪影$（i=1,2）$，让$ri$成为输出的三维物体中没有使用的块的体积之和。让$S$是两个对象中都使用了的块的集合。然后你会得到以下评价值。评价值越低越好。

$round(10^9\times (r_1+r_2+\sum_{i \in S}\frac{1}{v_i}))$

例如，如果区块集合由体积为5的区块A、体积为3的区块B和体积为2的区块C组成，如果第一组剪影是由可以用A和B创建的3D对象实现的，第二组剪影是由可以用A和C创建的3D对象实现的，那么得出的评价值是$round(10^9×(2+3+1/5))$。

对于每个测试案例，我们计算出相对分数$round(10^9×\frac{YOUR}{MIN}）$，其中$YOUR$是你的评价值，$MIN$是所有竞争者在该测试案例中获得的最低评价值。提交的分数是相对分数的总和。

最终的排名将由比赛结束后进行的有更多输入的系统测试来决定。在临时/系统测试中，如果你提交的文件产生非法输出或超过某些测试案例的时间限制，只有这些测试案例的分数将为零，你提交的文件将被排除在这些测试案例的$MIN$计算中。

系统测试将只针对最后一次提交的结果为.以$CE$外的内容进行。 请注意不要在最后提交时犯错。

测试案例的数量

临时测试：$50$ 系统测试：$2000$。我们将在比赛结束后公布$种子.txt（sha256=08db725cbdc37734a2e8fbe5bc0cbc1e95d7a68933b7f43dcdd0ffc3d2a95e34）。$ 系统测试包含$200$个输入，每个$D=5,6,⋯,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$是剪影图像的大小，每个剪影图像是$D\times\ D$的平方。 $5\leq\ D\leq 14$ 满足。
• $f_i,r_i$是第i$对剪影图像，其中$ f_i $是从正面看的剪影，$ r_i $是从右边看的剪影。 每个都是一个$ D/times/D $的01矩阵，并以长度为$ 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$。 这个条件确保总有一个实体与指定的一对剪影相匹配。

设$n$为块的总数。与第i对剪影相对应的区块排列用一个三维阵列$b$表示如下 $i (x,y,z)$的大小为$D×D×D$。 如果第$k(1≤k≤n)$个块占据了以$(x,y,z)$和$(x+1,y+1,z+1)$为对角线的立体区域，则$bi(x,y,z)=k；$如果没有一个块占据该区域，则$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)$

其中$b_i$是$b_i$的$x\times\ D^2+y\times\ D+z$输出，其中$b_i(x,y,z)$。对于每个$i=1,/cdots,n$，$i$的块必须至少在$b_1$或$b_2$中使用。 如果该区块在其中任何一个中都没有使用，那么它就被判定为WA。

显示例子

##样例输入 #1

样例输入 #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 3 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 0 0 9 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 11 12 12 0 13 0 0 0 12 14 0 0 0 0 14 0 0 0 14 14 0 0 0 0 14 0 0
15 0 0 0 0 3 14 0 0 0 0 3 0 0 0 0 9 16 0 0 0 9 9 0 0 0 0 17 0 0 0 0 0 0 14 0 10 0 0 3 14 0 0 10 0 9 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 12 0 12 0 0 9 0 0 0 0 0 0 0 0 0 0 3 14 0 0 7 0 0 0 7 0 5 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 7 0 0 0 5 0 0 0 0 0 0 0 0 0

呈现。

###得分。

让$v_1,cdots,v_n$为创建的玩具集中每个块的体积。这里，一个积木的体积等于组成它的$1\times\ 1\times\ 1$立方体的数量。每个积木必须是相连的，也就是说，通过将其组成的任何一个立方体移动到共享一个面的立方体中，可以到达。如果至少有一个未连接的方块，则确定为WA。请注意，每个区块必须是相连的，但由区块组合而成的立方体可能是不相连的。

对于$i=1,2$的一对剪影，让$r_i$为在制作输出立方体时未使用的块的体积之和，$S$为两者使用的块的集合。然后得到以下评价值。 评价值越低越好。

例如，如果一组积木由体积为5的积木A、体积为3的积木B和体积为2的积木C组成，第一组剪影是用可以用A和B创建的实体实现的，第二组剪影是用可以用A和C创建的实体实现的，那么得出的评价值是$\mathrm{round }\left(10^9\times\ \left(2+3+1/5\right)\right)$.

对于每个测试案例，会得到$mathrm{round}(10^9\times\frac{所有参与者中的最小评价值}{自己的评价值})$的**相对评价分数，其总和就是提交分数。

最终的排名是由更多输入的系统测试中的分数决定的，系统测试是在竞赛之后进行的。对于临时测试和系统测试，如果一些测试案例有错误的输出或超过时间限制，该测试案例的相对评价分数将为零，并且该测试案例将被排除在该测试案例的 "所有参赛者中的最低评价值 "的计算之外。注意不要在你提交的最后答案中出现错误，因为系统测试只会在最后提交的中进行，其结果不是CE。

测试案例的数量

• 临时测试：50
• 系统测试：2000个，（种子.txt）在比赛后发布
• 系统测试包含200美元的输入，每个输入使给定的剪影的大小为$D=5,6,\cdots,14$美元。
• $seed=0$的输入是手动创建的，不包括在临时和系统测试中。

关于相对评价系统

对于临时测试和系统测试，只有最后一次提交的结果不是CE的才会反映在排名表中。只有反映在排名表中的最后一个提交物也被用于计算所有参与者中每个测试案例的最低评分，用于计算相对评价得分。

排名表中显示的分数是一个相对评价分数，相对评价分数对每一个新提交的文件都要重新计算。另一方面，在提交列表中可以看到的每个提交的分数，是每个测试案例的评价值的原样之和，并不显示相对评价分数。要想知道除当前排名列表中的最新提交的案例以外的相对评价分数，需要重新提交。在输出不正确或超过时间限制的情况下，在提交列表中可以看到的分数是零，但排名表中显示的是回答正确的测试案例的相对分数之和。

关于执行时间

执行时间可能略有不同。此外，由于在系统测试中同时进行了大量的执行工作，已经证实了一个现象，与临时测试相比，执行时间增加了几个百分点。因此，在系统测试中，刚好低于执行时间限制的提交可能会导致TLE。请测量程序中的时间并终止程序或留出更多的执行时间。

示例方案。

下面是一个用Python编写的示例方案。该方案通过为所有$(x,y,z)$铺设$1\times\ 1\times\ 1$的块来实现所需的剪影，这样$f(z,x)=1$和$r(z,y)=1$。

<pre class="prettyprint linenums">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])))

输入生成方法。

用$\mathrm{randint}(L,U)$表示一个函数，该函数在$L$和$U$之间产生均匀的随机整数值。用$\mathrm{randdouble}(L,U)$表示在$L$和$U$之间均匀地随机生成浮动小数值的函数。

生成$D$

通过 $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$成为要生成的剪影数组，对于所有$(z,x)$，用$g(z,x)=0$初始化它。生成一个值$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$再次初始化为$0$，并从生成$m$开始。

###工具（输入生成器？ 展示器)

• 网络版：可进行三维显示。
• 本地版本: 要使用这个工具，你必须有一个Rust语言的编译环境。
  • Precompiled binaries for Windows: 如果你在设置Rust语言环境方面有困难，请用这个代替。

在比赛期间，只有种子=0的可视化器的输出图片（PNG）可以在twitter上分享。 请务必使用指定的标签并使用公共账户。 只能分享种子=0的可视化结果和分数，不能分享视频、输出字符串、分享其他种子的分数，也不能提到解决方案？ 不允许提及解决方案的方法或讨论。

共享图片列表