故事
AtCoder 有 n 仓库里的纸箱,分为 m 垂直堆叠。 每个盒子都贴有一个唯一的编号 1,\cdots,n,高桥社长想要按照编号从小到大的顺序将它们一件一件地运出仓库。 为了搬出一个盒子,他需要将其顶部的所有盒子移到另一堆盒子上。 由于高桥是一个非常强壮的人,他可以一次举起并移动尽可能多的箱子,但他消耗的能量取决于他举起的箱子的数量。 请找到一种消耗尽可能少的能量的方法来搬运箱子。
问题陈述
有 n 纸板箱,每个都标有唯一的编号 1,\cdots,n,分为 m 堆栈。 我们指的是标有数字的盒子 v(1\leq v\leq n) 作为“框 v”和 i(1\leq i\leq m)从左边算起第一个堆栈为“堆栈 i“。 堆叠数 m 是除数 n,以及每个堆栈 i 包含 n/m 框,带数字 b_{i,1},b_{i,2},\cdots,b_{i,n/m} 从下到上。
您可以重复以下两种类型的操作,最多可达 5000 次。
- 选择一个框 v (1\leq v\leq n) 尚未进行。拆下盒子 v 以及当前堆栈中其上方的所有框,并将它们移动到另一个堆栈的顶部 i(1\leq i\leq m) 以相同的顺序。假设在栈中 i' 到哪个箱子 v 属于,盒子已编号 b_{i',1}, \cdots, b_{i',h'} 从下到上, b_{i',j} = v。另外,假设目标堆栈中的框 i 已编号 b_{i,1}, \cdots, b_{i,h} 从下到上。此操作完成后,堆栈 i' 将变成 b_{i',1}, \cdots, b_{i',j-1},并堆栈 i 将变成 b_{i,1}, \cdots, b_{i,h}, b_{i',j}, \cdots, b_{i',h'}。设此操作移动的盒子数量为 k = h' - j + 1。然后, 将消耗 k+1 单位能量。如果 i=i',此操作没有任何改变,只是浪费能源。
- 如果剩余所有盒子中最小的数字是 v和盒子 v 位于堆栈顶部,然后是框 v 可以进行。该操作不消耗能量。
操作1无法创建新堆栈 i>m,但它可以将盒子移动到空堆栈中 i(1\leq i\leq m) 在通过操作 2 取出所有框后。
请找到一个操作序列,以尽可能少的总能量消耗执行所有框。
评分
如果所有方框都执行小于或等于 5000 操作,总能量消耗为 V,您将获得分数 \max(1, 10000-V)。 如果未能执行所有的框,或者输出非法的操作序列(指定超出范围的值或已经执行过的框,或者指定不满足操作2中的条件的框),则判断为 WA.
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
n m
b_{1,1} \cdots b_{1,n/m}
\vdots
b_{m,1} \cdots b_{m,n/m}
箱数 n 和堆栈数量 m 固定在 n=200 和 m=10 在所有测试用例中。 数量 b_{i,j} 代表的数量 j堆栈底部的第一个框 i,并且满足 1\leq b_{i,j}\leq n.
输出
让 k- 第一个操作由两个整数表示 (v_k,i_k) 如下。
- 如果使用操作 1 移动框 v(1\leq v\leq n) 并将其上堆放的所有盒子移至另一堆 i(1\leq i\leq m),然后 (v_k,i_k)=(v,i).
- 如果使用操作2进行框 v, (v_k,i_k)=(v,0).
输出获得的操作序列 (v_1,i_1),\cdots,(v_K,i_K) (K\leq 5000) 到标准输出,格式如下:
v_1 i_1 \vdots v_K i_K
输入生成
盒子编号是通过随机打乱整数来生成的 1 to n ,然后将它们分成几组 n/m 每个。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。