← 返回题目列表

AtCoder · ahc040_a

A. 包装不确定的矩形

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

故事

AtCoder 销售多种带有其徽标的限量版商品。 他们现在决定推出“特别套装”,以折扣价捆绑这些限量版商品。 高桥负责将传送带上一件一件交付的货物包装到一个纸板箱中,然后交给送货服务人员。 为了准备发射,他决定练习打包。

由于运费与纸箱的宽度和高度之和成正比,因此需要努力将货物包装到尽可能小的盒子中。 每件商品都是长方形的,但高桥没有测量工具,所以他用眼睛估算了宽度和高度,并通过电话向您这位优化专家咨询。

当您通过电话指示高桥如何安排货物时,他会按照您的指示并相应地安排物品。 然后,他通过肉眼估计该布置所需的纸板箱的宽度和高度,并将结果报告给您。 根据该信息,您为安排提供新的说明。

重复此过程,找到一种将所有货物包装到尽可能小的纸板箱中的安排。

问题陈述

你被给予 N 矩形。 的 i第一个矩形具有宽度 w_i 和身高 h_i。 对于每个矩形,观测值 w'_i=\mathrm{normal}(w_i, \sigma) 和 h'_i=\mathrm{normal}(h_i, \sigma) 作为输入提供,其中包括测量误差。 在这里, \mathrm{normal}(\mu, \sigma) 是一个通过以下步骤生成值的函数:

  1. 从具有均值的正态分布生成随机值 \mu 和标准差 \sigma.
  2. 将生成的值舍入为最接近的整数。
  3. 如果结果值小于 1,设置为 1,如果超过 10^9,设置为 10^9.

将这些矩形按照其索引顺序放置在平面上,以使它们不重叠。 每个矩形都可以旋转 90^\circ,如有必要,交换其宽度和高度。

积极 x- 轴向右延伸,正方向 y- 轴向下延伸。 矩形可以放置在 x \geq 0 和 y \geq 0。 您需要将放置方法指定为序列 (p_0, r_0, d_0, b_0), (p_1, r_1, d_1, b_1), \dots,这样:

  • p_i 表示要放置在的矩形的索引 i- 第一步 (0 \leq p_i \leq N-1). 您可以尝试只放置部分矩形,但索引必须按升序排列;换句话说,对于所有 i < j, p_i < p_j 必须保留。
  • r_i 表示矩形是否应旋转 90^\circ。如果 r_i = 0,矩形不旋转;如果 r_i = 1,矩形被旋转。
  • d_i 指定矩形的放置方向。
    • If d_i is U,矩形向上移动,直到停在已放置的另一个矩形的底边或该行处 y = 0.
    • If d_i is L,矩形向左移动,直到停在已放置的另一个矩形的右边缘或该行处 x = 0.
  • b_i 表示放置的参考矩形。 b_i 必须是 -1 或先前放置的矩形的索引。
    • 将矩形向上放置时 (U), b_i 指定哪个矩形的右边缘应与新矩形的左边缘对齐。如果 b_i = -1,矩形的左边缘与 x = 0.
    • 将矩形向左放置时 (L), b_i 指定哪个矩形的底边应与新矩形的顶边对齐。如果 b_i = -1,矩形的顶边与 y = 0.

操作示例

在下面的示例中,第三个矩形在不旋转的情况下放置,并针对每对说明了放置结果 (d, b).

操作 (d,b) 之前 (U,-1) (U,0) (U,1) (U,2)
结果
操作 (d,b) 之前 (L,-1) (L,0) (L,1) (L,2)
结果

重复以下操作 T 次:

  1. 指定如何放置矩形。请注意,放置从空状态开始,而不是从上一个放置继续。
  2. 放置后,让宽度(最大 x- 矩形存在的坐标)是 W,以及高度(最大 y- 矩形存在的坐标)是 H。然后,测量值 获得 W' = \mathrm{normal}(W, \sigma) 和 H' = \mathrm{normal}(H, \sigma) 作为测量结果。

评分

让 W_t 和 H_t 是放置位置的宽度和高度 t分别第-回合,并让 U_t 是本轮中未使用的矩形集。然后,分数 s_t 为 t第回合定义如下:

\[ s_t = W_t + H_t + \sum_{i\in U_t}(w_i+h_i) \]

那么你获得的绝对分数为 \min_t s_t. 绝对分数越低越好。

对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。

最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:3000。我们将发布 种子.txt (sha256=1e93374aa02130a1167c2893f1904b4234a3b517d1e7b9d25022a9125ff3777d) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

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

输入和输出

一、矩形数量 N,操作圈数 T,标准差 \sigma 的测量误差和测量的尺寸 每个矩形的 w'_i 和 h'_i 由标准输入以以下格式给出。

N T \sigma
w'_0 h'_0
\vdots
w'_{N-1} h'_{N-1}
  • 矩形的数量 N 满足 30 \leq N \leq 100.
  • 操作次数 T 满足 N/2 \leq T \leq 4N.
  • 测量误差的标准偏差 \sigma 是满足以下条件的整数 1000 \leq \sigma \leq 10000.
  • 宽度和高度的测量值, w'_i 和 h'_i,是之间的整数 1 和 10^9 包括在内。

阅读以上信息后,重复以下过程 T 次。

让表示矩形放置方法的序列为 (p_0, r_0, d_0, b_0), (p_1, r_1, d_1, b_1), \dots, (p_{n-1}, r_{n-1}, d_{n-1}, b_{n-1})。 在这里, n 表示要放置的矩形的数量,以及 n 可能小于 N。 按以下格式将此序列输出到标准输出。

n
p_0 r_0 d_0 b_0
\vdots 
p_{n-1} r_{n-1} d_{n-1} b_{n-1}

输出后,宽度和高度的测量值, W' 和 H'是从标准输入以以下格式给出的。

W' H'

输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.

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

示例

t 输出 输入
先前信息
4 3 1000
77685 46130
32459 75368
54192 88183
60740 42948
1
2
0 0 U -1
1 1 U 0
153220 47195
2
4
0 0 U -1
1 1 L -1
2 1 L 1
3 0 U -1
167543 86611
3
4
0 0 U -1
1 0 L -1
2 0 U -1
3 0 U 2
113031 134437

显示示例

示例解决方案

这是 Python 中的示例解决方案。该程序尝试将每个矩形放置在随机旋转和位置中 T 次。
import random

def query(prdb):
    print(len(prdb))
    for p, r, d, b in prdb:
        print(p, r, d, b)
    W, H = map(int, input().split())
    return W, H

N, T, sigma = map(int, input().split())
wh = [tuple(map(int, input().split())) for _ in range(N)]

rng = random.Random(1234)

for _ in range(T):
    prdb = []
    for i in range(N):
        prdb.append((
            i,
            rng.randint(0, 1),
            ['U', 'L'][rng.randint(0, 1)],
            rng.randint(-1, i - 1),
        ))
    query(prdb)

输入生成

  • \mathrm{rand}(L,U): 均匀地随机生成一个整数 L 和 U,包括在内。
  • \mathrm{rand\_double}(L,U): 均匀地随机生成一个实数 L 和 U,包括在内。

的一代 N, T,和 \sigma

  • N = \mathrm{rand}(30, 100)
  • T = \mathrm{round}(N \times 2^{\mathrm{rand\_double}(-1, 2)})
  • \sigma = \mathrm{rand}(1000, 10000)

的一代 w 和 h

让 U = 10^5,并生成 生成 L = \mathrm{rand}(U/10, U/2).
对于每个 i, w_i = \mathrm{rand}(L, U) 和 h_i = \mathrm{rand}(L, U) 。

工具(输入生成器、本地测试器和可视化器)

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

工具使用的输入文件规范

提供给本地测试器的输入文件包括以下格式的附加信息,附加到提供给解决方案程序的先验信息的末尾。

w_0 h_0
\vdots
w_{N-1} h_{N-1}
dW_0 dH_0
\vdots
dW_{T-1} dH_{T-1}
  • w_i 和 h_i 代表真实的宽度和高度 i- 第一个矩形。
  • dW_t 和 dH_t 是添加到结果中的测量误差 t第回合。