AT_ahc031_a.[AHC031A] Event Hall

有一个可以用纵横长度均为 $W$ 的网格表示的活动大厅。最左上角的格点坐标为 $(0,0)$，从这里向下走 $i$ 格、向右走 $j$ 格后的格点坐标为 $(i,j)$。最右下角的格点坐标为 $(W, W)$。

给定 $D$ 天的预约情况。每一天的预约数均为 $N$，第 $d=0,1,\cdots,D-1$ 天的第 $k=0,1,\cdots,N-1$ 个预约希望租用面积不少于 $a_{d,k}$ 的矩形区域。所出租的矩形的形状和位置可以自由选择，但必须与坐标轴平行，且每个顶点都必须在格点上。此外，同一天内不同预约对应的矩形不能有正面积的重叠。未被出租的空余空间可以保留。

对于第 $d$ 天第 $k$ 个预约，所出租的矩形区域记为 $R_{d,k}$，其面积为 $b_{d,k}$。若 $a_{d,k} > b_{d,k}$，则会产生 $100\times(a_{d,k}-b_{d,k})$ 的费用；若 $a_{d,k}\leq b_{d,k}$，则不会产生费用。

对于每个矩形 $R_{d,k}$，其外周中不属于网格外周的部分需要设置隔断，相反，其他地方不得设置隔断。在第 $d$ 天，需要根据第 $d-1$ 天的隔断配置，进行隔断的安装和拆除以满足上述条件。第 $d$ 天安装和拆除的隔断总长度为 $L_d$ 时，会产生 $L_d$ 的费用。但特别地，第一天规定 $L_0=0$。

更详细地，$L_d$ 的计算如下。对于每个 $d=0,\cdots,D-1$，对于网格内部（不包括外周）的每一条横向线段 $(i,j)-(i,j+1)$（$1\leq i\leq W-1,\ 0\leq j\leq W-1$），若该线段在某个 $R_{d,k}$ 的外周上，则定义 $H_{d,i,j}=1$，否则 $H_{d,i,j}=0$。此时，若 $H_{d-1,i,j}\neq H_{d,i,j}$，则 $L_d$ 增加 1。类似地，对于每一条纵向线段 $(i,j)-(i+1,j)$（$0\leq i\leq W-1,\ 1\leq j\leq W-1$），若该线段在某个 $R_{d,k}$ 的外周上，则定义 $V_{d,i,j}=1$，否则 $V_{d,i,j}=0$。此时，若 $V_{d-1,i,j}\neq V_{d,i,j}$，则 $L_d$ 增加 1。

请决定每一天每个预约所分配的矩形区域，使得总费用尽可能小。

输入通过标准输入给出，格式如下：

$W$ $D$ $N$ $a_{0,0}$ $ \cdots $ $a_{0,N-1}$
$ \vdots $
$a_{D-1,0}$ $ \cdots $ $a_{D-1,N-1}$

• 网格的纵横长度 $W$ 固定为 $W=1000$。
• 天数 $D$ 满足 $5\leq D\leq 50$。
• 每天的预约数 $N$ 满足 $5\leq N\leq 50$。
• 第 $d$ 天第 $k$ 个预约希望的面积 $a_{d,k}$ 是满足 $1\leq a_{d,0}\leq \cdots\leq a_{d,N-1}$ 的整数，且 $a_{d,0}+\cdots+a_{d,N-1}\leq W^2$。

对于第 $d$ 天第 $k$ 个预约，若分配的矩形左上角顶点坐标为 $(i_{d,k},j_{d,k})$，右下角顶点坐标为 $(i_{d,k}',j_{d,k}')$，则请按如下格式输出到标准输出：

$i_{0,0}$ $j_{0,0}$ $i_{0,0}'$ $j_{0,0}'$
$ \vdots $
$i_{0,N-1}$ $j_{0,N-1}$ $i_{0,N-1}'$ $j_{0,N-1}'$
$ \vdots $
$i_{D-1,0}$ $j_{D-1,0}$ $i_{D-1,0}'$ $j_{D-1,0}'$
$ \vdots $
$i_{D-1,N-1}$ $j_{D-1,N-1}$ $i_{D-1,N-1}'$ $j_{D-1,N-1}'$

每个矩形必须满足 $0\leq i_{d,k}<i_{d,k}'\leq W$ 且 $0\leq j_{d,k}<j_{d,k}'\leq W$。若不满足此条件，将被判定为 WA。

查看示例

故事背景

高桥君负责管理一个活动大厅。这个大厅可以通过设置隔断分割成若干矩形区域，并将每个区域分别出租给不同的团体。

给定数天的预约情况。每个预约指定了希望的区域面积，如果分配的区域面积小于指定面积，则会产生费用。同时，改变区域分割所需的隔断安装和拆除也会产生与长度成正比的费用。请你尽可能降低总费用来运营活动大厅。

得分

$D$ 天的总费用为 $C$ 时，绝对得分为 $C+1$。绝对得分越小越好。

每个测试用例，得分为 $ \mathrm{round}(10^9\times\frac{\text{所有参赛者中的最小绝对得分}}{\text{你的绝对得分}}) $，相对评价得分为所有测试用例的得分之和。

最终排名将在比赛结束后，对更多输入进行系统测试后决定。无论是暂定测试还是系统测试，若某些测试用例输出不合法或超时，则该测试用例的相对评价得分为 0，并且该用例不会计入“所有参赛者中的最小绝对得分”的计算。系统测试只针对最后一次非 CE 的提交，请务必确保最终提交的解答正确。

测试用例数量

• 暂定测试：50 个
• 系统测试：2000 个，比赛结束后将公开 seeds.txt (sha256=16f021f46aad43a81ad05ebf38ed2b6ac813eafacbb6ad98549832218314db8f)

关于相对评价系统

无论是暂定测试还是系统测试，只有最后一次非 CE 的提交会计入排行榜。用于计算每个测试用例“所有参赛者中的最小绝对得分”时，也只考虑排行榜上的最终提交。

排行榜上显示的是相对评价得分，每次新提交都会重新计算。提交列表中显示的分数是所有测试用例的绝对得分之和，不显示相对评价得分。若想了解非最新提交在当前排行榜下的相对评价得分，需要重新提交。若输出不合法或超时，提交列表中的分数为 0，但排行榜会显示所有正确测试用例的相对得分之和。

关于运行时间

运行时间会有一定波动。系统测试时由于同时运行大量程序，运行时间通常比暂定测试长几个百分点。因此，接近时间限制的提交在系统测试中可能会超时。建议在程序中自行计时并提前终止，或预留足够的运行时间。

示例程序

以下为 Python 示例程序。该程序将第 $k$ 个矩形分配为左上角 $(k,0)$，右下角 $(k+1,W)$。

# read input
W, D, N = map(int, input().split())
a = []
for d in range(D):
    a.append(list(map(int, input().split())))

# determine rectangles
rect = [[] for _ in range(D)]
for d in range(D):
    for k in range(N):
        rect[d].append((k, 0, k + 1, W))

# output
for d in range(D):
    for k in range(N):
        i0, j0, i1, j1 = rect[d][k]
        print(i0, j0, i1, j1)

输入生成方法

用 $ \mathrm{rand}(L,U) $ 表示生成 $L$ 到 $U$ 之间的均匀随机整数。

天数 $D$ 由 $D=\mathrm{rand}(5,50)$ 生成。每天预约数 $N$ 由 $N=\mathrm{rand}(5,50)$ 生成。参数 $e$ 由 $e=\mathrm{rand}(500,5000)/10000$ 生成，平均空余面积 $E$ 设为 $E=\mathrm{round}(W^2 e^2)$。对于每个 $d=0,\cdots,D-1$，按如下方法生成 $a_{d,0},\cdots,a_{d,N-1}$：

首先，生成 $T_d=\mathrm{rand}(W^2-\mathrm{floor}(\frac{3E}{2}),W^2-\mathrm{floor}(\frac{E}{2}))$。然后，从集合 $S=\{0,T_d\}$ 开始，直到 $S$ 的元素数为 $N+1$，每次生成 $ \mathrm{rand}(1,T_d-1) $ 并加入 $S$。将 $S$ 的元素按升序排列为 $s_0(=0),s_1,\cdots,s_{N-1},s_N(=T_d)$，则 $a_{d,k}=s_{k+1}-s_k$。最后将 $a_{d,0},\cdots,a_{d,N-1}$ 升序排列。

工具（输入生成器与可视化工具）

• 网页版：比本地版更高性能，支持动画显示。
• 本地版：需安装 Rust 语言 编译环境。
  • Windows 版编译好的二进制：不想配置 Rust 环境可直接使用。

比赛期间，禁止分享可视化结果、解法或讨论。请注意遵守规则。

由 ChatGPT 4.1 翻译