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}

### 故事背景 高桥君负责管理一个活动大厅。这个大厅可以通过设置隔断分割成若干矩形区域，并将每个区域分别出租给不同的团体。 给定数天的预约情况。每个预约指定了希望的区域面积，如果分配的区域面积小于指定面积，则会产生费用。同时，改变区域分割所需的隔断安装和拆除也会产生与长度成正比的费用。请你尽可能降低总费用来运营活动大厅。 ### 得分 $D$ 天的总费用为 $C$ 时，绝对得分为 $C+1$。**绝对得分越小越好。** 每个测试用例，得分为 $ \mathrm{round}(10^9\times\frac{\text{所有参赛者中的最小绝对得分}}{\text{你的绝对得分}}) $，**相对评价得分**为所有测试用例的得分之和。 最终排名将在比赛结束后，对更多输入进行系统测试后决定。无论是暂定测试还是系统测试，若某些测试用例输出不合法或超时，则该测试用例的相对评价得分为 0，并且该用例不会计入“所有参赛者中的最小绝对得分”的计算。系统测试只针对**最后一次非 CE 的提交**，请务必确保最终提交的解答正确。 #### 测试用例数量 - 暂定测试：50 个 - 系统测试：2000 个，比赛结束后将公开 [seeds.txt](https://img.atcoder.jp/ahc031/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}$ 升序排列。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc031/PJcas1sL.html?lang=ja)：比本地版更高性能，支持动画显示。 - [本地版](https://img.atcoder.jp/ahc031/PJcas1sL.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制](https://img.atcoder.jp/ahc031/PJcas1sL_windows.zip)：不想配置 Rust 环境可直接使用。 比赛期间，禁止分享可视化结果、解法或讨论。请注意遵守规则。 由 ChatGPT 4.1 翻译