故事
高桥管理着一个活动大厅。 这个活动大厅可以通过安装隔断分成几个矩形区域,每个区域出租给不同的团体。
您将获得几天的预订状态。 每次预订都会指定所需的路段面积,如果指定的路段面积小于指定面积,则会产生费用。 另外,安装和拆除隔板以改变部分的划分会产生基于隔板长度的成本。 请尽量减少总成本来运营活动厅。
问题陈述
有一个以网格表示的活动大厅,其垂直和水平长度均为 W。 让 (0,0) 是左上角网格点的坐标,并且 (i,j) 为网格点的坐标 i 向下平方并 从那里向右走 j 方块。 右下网格点的坐标为 (W, W).
您将获得以下预订状态 D 天。 每天预约人数均为 N,以及 k=0,1,\cdots,N-1当天第 次预订 d=0,1,\cdots,D-1 希望租用至少面积的矩形部分 a_{d,k}。 租用的矩形的形状和位置是灵活的,但它们必须与轴平行,并且每个顶点必须是一个网格点。 此外,同一天两个不同预订的矩形不得具有共同的正面积。 存在一些未出租的空置空间是可以接受的。
让 R_{d,k} 是矩形 k当天第 次预订 d 和 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,您必须在 day 的配置中安装和删除分区 d-1 满足这个条件。 如果当天安装和拆除的分区总长度 产生了 d is 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)在内部,不包括网格的周长,我们定义 H_{d,i,j}=1 如果它位于任何 R_{d,k},否则我们定义 H_{d,i,j}=0。 然后加1 L_d 对于每个 (i,j) 这样 H_{d-1,i,j}\neq H_{d,i,j}。 类似地,对于每个垂直线段 (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。 然后加1 L_d 对于每个 (i,j) 这样 V_{d-1,i,j}\neq V_{d,i,j}.
您的任务是确定要出租的矩形部分,以使总成本尽可能小。
评分
当总成本为 D 天是 C,您获得的绝对分数为 C+1. 绝对分数越低越好。
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=16f021f46aad43a81ad05ebf38ed2b6ac813eafacbb6ad98549832218314db8f) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出。
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.
- 所需区域 a_{d,k} 的 k当天第 次预订 d 是满足以下条件的整数值 1\leq a_{d,0}\leq \cdots\leq a_{d,N-1} 其总和满足 a_{d,0}+\cdots+a_{d,N-1}\leq W^2.
输出
出租左上角顶点有坐标的矩形时 (i_{d,k},j_{d,k}) 且其右下顶点有坐标 (i_{d,k}',j_{d,k}') 为 k当天第 次预订 d,按以下格式输出到标准输出。
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}\lt i_{d,k}'\leq W 和 0\leq j_{d,k}\lt j_{d,k}'\leq W。 如果不满足此条件,提交将被判定为 WA.
示例解决方案
这是 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 by D=\mathrm{rand}(5,50)。 我们生成预订数量 N 每天由 N=\mathrm{rand}(5,50)。 一个参数 e 是由生成的 e=\mathrm{rand}(500,5000)/10000 我们设置平均可用区域 E to 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\},生成 \mathrm{rand}(1,T_d-1) 并将其添加到 S 直到元素数量 S 变为 分别为 N+1。 让 s_0(=0),s_1,\cdots,s_{N-1},s_N(=T_d) 是结果的元素 S,按升序排列。 然后我们设置 a_{d,k}=s_{k+1}-s_k。 最后,排序 a_{d,0},\cdots,a_{d,N-1} 按升序排列。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
1000 5 10 6508 11666 12167 16717 46095 55928 56542 127260 200961 202211 11754 15667 26620 31851 48890 50181 52520 53150 263650 280526 7171 7218 14268 26231 37133 47199 93385 131356 174634 189807 10290 15811 16235 39805 45168 75830 76161 137648 148368 152504 6553 22994 44284 45120 67646 68899 98726 129109 138615 247097
示例输出 1
0 43 23 326 747 654 824 843 863 2 1000 469 824 621 892 869 892 469 983 977 23 19 676 105 58 917 742 1000 494 398 747 917 85 105 863 398 6 398 403 911 166 917 329 1000 6 848 266 911 403 803 588 1000 863 633 983 977 361 19 494 398 361 398 494 803 494 105 588 767 863 0 1000 633 588 0 863 1000 0 19 361 848 10 740 81 841 949 196 1000 425 538 396 588 764 883 425 988 748 0 0 189 268 0 268 189 540 588 396 883 764 515 76 949 396 81 767 873 1000 189 0 515 583 363 460 538 767 363 767 600 923 762 767 873 923 288 923 807 1000 0 0 1000 76 188 397 363 832 10 376 188 841 0 76 462 376 515 76 949 425 538 425 988 764 10 376 86 736 288 452 330 1000 1 76 243 265 349 283 604 460 86 397 288 736 0 736 288 1000 243 8 604 283 330 520 600 1000 600 638 1000 1000 604 0 1000 638