問題文
丰田汽车公司用集装箱运输大量货物。 给定一组行李的数据和集装箱的尺寸,输出将所有行李正确装入集装箱的方法。 虽然项目加载的顺序是任意的,但为了使加载过程更加高效,建议项目尽可能按照相同的顺序加载。
集装箱规格
容器是水平的 W、縦 H,高度 D 长方体的四个角具有底面。 B\times B 正方形与高度 D 它具有四个长方体块的形状。 下图显示了从正上方观察时容器的形状。

我无法将行李放置在有四个角块的区域,我想将其装载到其他区域。 容器的高度为 D 然而,在这个问题中,D 可以将货物装载到更高的位置。但容器的高度 如果车辆装载到超过 D 的位置,它将获得极低的评级。
行李规格
所有行李 M 有不同的类型,并且它们具有以下属性。
- 所有行李都是长方体,i 行李类型的尺寸为 w_i、縦 h_i,高度 d_i 。
- i 所有类型的行李均 a_i 。
- 每件行李箱可以绕每个轴以 90 度增量旋转,但某些类型的行李箱仅允许在底部固定的情况下旋转。i 标记了行李类型的轮换限制 f_i 什么时候可以工作f_i 是
在
Y可以自由旋转,f_i 是 在N只能在底部固定的情况下旋转。 - 根据行李的类型,是否可以在其上面堆放其他行李有限制。i 标志表示是否允许将物品放置在该类型行李的顶部。
当 g_i 什么时候可以工作g_i 是
在
Y时,可以将东西放在上面,g_i 是 在N时,请勿在其上面放置任何物品。这里,“行李A放置在行李B的上面”是指行李A的底面和行李B的顶面的公共部分具有正面积。即使行李 A 放置在行李 B 上方的空间内,如果行李 B 之间存在间隙,也不会被视为放置在行李 B 的上方。
如何装载行李
从上方垂直降低物品,一件一件地装载物品。 因此,在计划放置该物品的位置上方的空间中不得有其他已放置的物品。 装载前可以将货物旋转90度,但货物的每一侧必须与集装箱的侧面和底部平行。 装载的行李是 6 割(向下舍入到最接近的整数)这些必须与集装箱或其他货物的底部接触。 集装箱高度 即使将货物装载到超过 D 的位置,货物也不能放置在集装箱外部或四个角块上方。
您可以按任何顺序加载项目(但是,如果您按照您想要的顺序加载它们,您将获得更好的分数)。 无需一次性装载同一类型的行李;也可以装载第一件A类型行李→第一件B类型行李→第二件A类型行李,以此类推。
得点
i 待装载货物类型 p_i (0\leq p_i\leq M-1),装载货物顶面的最大高度为 \mathrm{MaxHeight} 。 在这种情况下,将给予以下处罚: 处罚越低越好。
(ペナルティ) = 1000 + \mathrm{MaxHeight} + (順番前後ペナルティ) + (収容失敗ペナルティ)
回合前后的罚分为p 跌倒次数 1000 次。也就是说,i < j 并且, 如果您对满足p_i > p_j 对于 (i,j) 对,将应用订单前后的罚分。 1000 积分已添加。
收容失败惩罚是 在\mathrm{MaxHeight}\leq D 的情况下 0 ,否则顶部高度为 D 超出的行李体积总和(行李本身的体积,不是超出部分的体积) E 当1000000 + 1000 E 变为。
对于每个测试用例,\mathrm{round}(10^9\times \frac{全参加者中の最小ペナルティ}{自身のペナルティ}) 可以得到第相对评价分数 将得到,其总和即为提交分数。
最终排名将根据比赛结束后进行的系统测试得分确定。 无论是临时测试还是系统测试,如果某些测试用例输出错误或超过时限,则该测试用例的相对评价分数将为0分,并且该测试用例将被排除在“所有参与者最低处罚”的计算之外。 系统测试 最后一次提交的结果不是 CE 这只会针对执行,因此请小心不要在您提交的最终答案中出现任何错误。
测试用例数量 用
- 初步测试:50件
- 系统测试:3000枚,比赛结束后 种子.txt (sha256=dfa7c8bc75f309e6c260506e3b354eaf9b7bfb2ef61d1bdaacebc8263c50dd70) 已发布
关于相关评价体系
中期测试和系统测试。CE 之外的结果才会反映在排名中。 仅使用排名表中反映的最终提交结果来计算每个测试用例的所有参与者的最低罚分,并用于计算相对评估分数。
排名表中显示的分数为相对评价分数,每次有新提交时都会重新计算相对评价分数。 另一方面,从提交列表中可以确认的每个提交的分数是每个测试用例的罚分之和,并且不显示相对评估分数。 需要重新提交才能了解非最新提交的当前排名的相对评估分数。 如果输出不正确或超过时间限制,则从提交列表中可以确认的分数将为0,但排名表将显示正确回答的测试用例的相对分数总和。
关于执行时间
执行时间会有一些波动。 此外,由于系统测试同时执行大量测试,因此我们观察到执行时间比临时测试增加几个百分点的现象。 因此,接近执行时限的提交就是系统测试。TLE。 请测量程序内的时间并中止该进程,或者留出额外的执行时间。
入力
输入是按以下格式从标准输入给出的。 w, h 的顺序错误,因此我们修复了它。为了避免修改工具,W, H 的顺序和对应关系会颠倒,会很混乱,但容器大小如下图。 按照 W H 的顺序,行李的尺寸为 h w 。 csv 文件是 订单是 w,h,d 。
M W H B D
h_0 w_0 d_0 a_0 f_0 g_0
h_1 w_1 d_1 a_1 f_1 g_1
:
h_{M-1} w_{M-1} d_{M-1} a_{M-1} f_{M-1} g_{M-1}
- 行李类型数量 大于或等于 M 是 可以表示为1 的整数。
- 容器和四个角块的尺寸为 W = 1120、H = 680、B = 30、D\in\{600,1200\} 很满意。
- 每件行李的尺寸 (w_i,h_i,d_i) 的组合是 该 csv 文件 匹配 中列出的任何一个。
- 行李件数 a_i 是 您也可以写 1 以上 30 的整数。 一个整数
- 行李轮换限制标志 f_i 和堆栈限制标志 g_i 是
您也可以写
Y或N。
出力
横向 x 轴,垂直 y 轴、高度方向 z 取轴。 容器所占面积(包括块部分)为 [0,W]\times[0,H]\times[0,D] 。 行李总数 N=\sum_{i=0}^{M-1} a_i 。 i 待装载货物类型 p_i (0\leq p_i\leq M-1)。 i 待装载货物的位置是距原点最近的货物角点的坐标。 (x_i,y_i,z_i) 和方向确定如下。 让我们用 r_i 来表达。 当
- r_i = 0 时,水平 (w_{p_i}) 边是水平轴,垂直轴 放置 (h_{p_i}) ,使侧面与垂直轴平行。 当
- r_i = 1 时,垂直 (h_{p_i}) 的边为横轴, 当 (w_{p_i}) ,使侧面与垂直轴平行。 当
- r_i = 2 时,高度 (d_{p_i}) 边是水平轴,垂直轴 放置 (h_{p_i}) ,使侧面与垂直轴平行。 当
- r_i = 3 时,垂直 (h_{p_i}) 边是水平轴,高度 (d_{p_i}) ,使侧面与垂直轴平行。 当
- r_i = 4 时,高度 (d_{p_i}) 的边为横轴, 当 (w_{p_i}) ,使侧面与垂直轴平行。 当
- r_i = 5 时,水平 (w_{p_i}) 边是水平轴,高度 (d_{p_i}) ,使侧面与垂直轴平行。 当
例如,r_i=0 ,行李占用的面积为
行李为 [x_i,x_i+w_{p_i}]\times[y_i,y_i+h_{p_i}]\times[z_i,z_i+d_{p_i}] 变为。
f_{p_i} 是
在 N 行李就是 i 只允许底部固定的情况下旋转,所以
必须是r_i 的值为
等于 0 或 1 。
另外,(x_i,y_i,z_i) 必须是整数坐标。
此时,按以下格式输出到标准输出。
p_0 r_0 x_0 y_0 z_0
p_1 r_1 x_1 y_1 z_1
:
p_{N-1} r_{N-1} x_{N-1} y_{N-1} z_{N-1}
入力生成方法
- D=600 你想要_____吗 D=1200 或随机选择容器的体积。 V 不包括四个角的区块区域 V=WHD-4B^2D 。
- 两个参数 由 V_{min}, V_{max} 该值应乘以 V_{min}=\mathrm{rand}(\lceil 0.3 V\rceil,\lfloor 0.8 V\rfloor), V_{max}=V_{min}+\lfloor 0.1 V\rfloor 确定。
- 从一组空行李开始,使用以下方法计算行李的总体积。 V_{min} 将行李种类一一增加,直至达到上述数量。
- 添加行李 行李候选清单 从 中随机选择(已经选择的可以再次选择)。
- 要添加的包数
确定 a_i 。确定数量的方法取决于包装的体积。
- 音量为 5\times 10^7 或更多, 使用以下方法随机确定a_i=1。
- 音量为 5\times 10^7 未満 10^7 或更多, 使用以下方法随机确定a_i 是 您也可以写 1 ~ 3 。 如果小于
- 音量为 10^7 未満 2.5\times 10^6 或更多, 使用以下方法随机确定a_i 是 您也可以写 1 ~ 10 。 如果小于
- 音量为 2.5\times 10^6 ,a_i 是 您也可以写 1 ~ 30 。 如果小于
- 随机确定行李件数时, 与 a 的概率为 a^{-2} 成正比。例如 1 ~ 3 从里面 2 的概率为 2^{-2}/(1^{-2}+2^{-2}+3^{-2}) 。
- 行李总体积为 V_{min} 处理完成后,总体积为V_{max} 如果更大,则清空行李组并重做创建行李组的过程。 在小于
- 実数 F 该值应乘以 0 以上 0.3 的实数之间随机生成。每件行李
关于 i 的概率 F 在 f_i 该值应乘以
N以及其他 通过初始化Y。 - 各荷物 i 关于 g_i 该值应乘以
Y并重复以下过程, g 。- 有 50% 的概率, 完成更改g 的过程。 一个随机包
- g_i =
Y选择 i 。如果不是,则终止。 将其更改为 - g_i 该值应乘以
N。然而,g_i 是 在N货物底部面积的总和就是集装箱的底部面积。 WH-4B^2 可以得到第 6 如果它变得大于百分比, 返回 g_i 该值应乘以Y,g 的过程。 一个随机包
工具(输入生成器·可视化器)
- 网页版:比本地版本性能更高,可以显示动画。
- 本地版本:使用方法Rust 语言
请为准备编译环境。
大于或等于输入生成程序执行时出现错误,因此已替换为修订版本。请重新下载。
- Windows用的已编译二进制文件:对于觉得构建 Rust 语言环境麻烦的人,请改用此文件。
比赛期间,您可以分享任何种子的可视化工具(官方或自制)的输出图像和视频,并提及解决方案和注意事项。 虽然不是必需的,Twitter 话题标签 #TOYOTAHC2023SPRING 请使用。
入力例 1
4 1120 680 30 1200 355 360 285 3 Y Y 155 210 120 1 Y Y 510 820 380 1 Y N 370 710 330 1 Y Y
出力例 1
0 0 0 30 0 0 1 360 30 0 0 0 715 0 0 1 1 0 385 0 3 0 30 30 285 2 0 0 30 615