故事
AtCoder Inc. 决定搬到新办公室。 为了降低成本,首席执行官高桥将亲自搬家,而不是聘请搬家公司。
旧办公室的地板上堆满了大量的纸箱,必须全部运到门口。 箱子可以堆叠起来并一次搬运多个,但如果堆得太重,它们可能会因自重而倒塌。
你的任务是找到一种方法,用尽可能少的动作将所有箱子安全地运送到入口处。
问题陈述
有一个办公室,包括 N \times N 方块。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 办公室入口位于广场 (0, 0).
最初,除了入口之外,每个方格都放置一个纸板箱。每个纸板箱有两个数值: 重量 和 耐用性。正方形的盒子 (i, j) 的重量为 w_{i,j} 和耐用性 d_{i,j}.
纸板箱可以垂直堆叠以一次携带多个箱子。 从初始位置开始 (0,0),高桥的目标是通过重复执行以下操作将所有箱子搬出办公室:
- 拾取当前位置的纸板箱。如果已有盒子,请将新盒子放在上面。如果当前位置没有盒子,则无法执行此操作。
- 将手中最上面的盒子放在当前位置。如果该方块中已经有一个框,则无法执行此操作。
- 沿四个方向之一移动到相邻的方块:上、下、左或右。允许移动到有盒子的方格上,但移动到盒子之外 不允许使用 N \times N 区域。
高桥非常坚固,可以搬运任意数量的箱子,无论总重量如何。 然而,当他移动时(操作 3),他所持有的盒子的耐用性会降低。 耐久度降到0以下的箱子会被压碎,判定为 WA.
盒子的耐久度降低量等于堆叠在其上方的所有盒子的总重量。具体来说,如果当前持有的盒子有重量 w_1, w_2, \ldots, w_n 从下到上,然后 i从底部数第一个框 (1 \le i \le n) 将丢失 \sum_{j=i+1}^n w_j 每次移动的耐久度。
耐久性仅在移动期间降低(操作 3)。在拾取或放置盒子(操作 1 和 2)期间它不会改变。将盒子放在地板上后,耐用性也不会恢复。
移动到入口处时 (0, 0) 使用操作3,当前持有的所有箱子均被带出办公室。
您最多可以执行 总计 2 \times N^3 操作。你的任务是用尽可能少的动作搬出所有的纸板箱。
评分
让 T 是执行操作 3(移动)的次数,令 R 是办公室中剩余的纸板箱数量。 分数计算如下:
- If R > 0: N^2 - R
- If R = 0: N^2 + 2 \times N^3 - T
在这里, T 仅统计操作3(移动)执行的次数;操作 1(拾取)和 2(放置)不包括在 T。 但是,操作总数的限制(最多 2 \times N^3) 适用于所有操作。
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N
w_{0,0} \cdots w_{0,N-1}
\vdots
w_{N-1,0} \cdots w_{N-1,N-1}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
- 在所有测试用例中, N 固定为 20。
- w_{i,j} 是一个整数,表示放置在正方形中的纸板箱的重量 (i, j)。因为广场上没有盒子 (0,0),我们有 w_{0,0} = 0。对于所有其他正方形, 1 \leq w_{i,j} \leq 10^3.
- d_{i,j} 是一个整数,代表放置在正方形的纸板箱的耐用度 (i, j)。在广场 (0,0), d_{0,0} = 0。对于所有其他正方形, 10 \leq d_{i,j} \leq 3\times 10^4.
输出
让操作依次执行 t 由单个字符表示 a_t 如下:
- 如果执行操作 1:
1 - 如果执行操作 2:
2 - 如果执行操作 3:
上:U
向下:D
左:L
右:R
让 L 是操作次数。 然后,按以下格式输出到标准输出:
a_0
\vdots
a_{L-1}
输入生成
- \mathrm{rand\_double}(L,U): 生成一个均匀随机的实数 L 和 U.
的生成 w
对于每个方块 (i, j) 除了 (0, 0), 我们生成 w_{i,j} as \mathrm{round}(\mathrm{rand\_double}(1, \sqrt{1000})^2).
的生成 d
对于每个方块 (i, j) 除了 (0, 0), 我们生成 d_{i,j} as \mathrm{round}(w_{i,j} \times \mathrm{rand\_double}(10, 30)).
工具(输入生成器和可视化工具)
- 网页版:这比提供动画和手动播放的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
20 0 3 749 809 20 263 83 30 559 8 5 269 675 47 235 204 747 216 134 244 2 651 130 557 93 426 690 873 506 98 22 251 213 814 874 79 857 6 158 639 2 965 45 107 259 20 957 244 18 962 152 82 327 226 24 131 99 1 255 60 177 1 42 878 353 185 89 656 757 54 351 349 489 249 679 756 191 395 719 145 613 203 741 455 1 402 877 791 146 956 506 262 280 746 156 733 66 237 389 115 164 738 84 747 10 579 81 6 78 215 337 556 479 498 2 674 120 737 429 106 872 394 35 325 49 6 129 185 45 218 18 892 162 7 419 579 768 11 724 266 29 236 832 372 132 857 840 10 446 74 734 199 148 802 24 467 321 410 237 50 715 391 412 13 312 2 138 645 333 260 621 736 483 876 62 9 44 77 180 3 165 852 738 29 110 119 857 974 104 103 886 500 271 819 155 467 579 108 466 837 243 39 711 197 494 17 800 721 15 193 138 5 451 736 311 272 582 177 112 533 441 65 2 544 545 259 147 10 101 411 23 144 449 18 668 211 497 475 470 867 179 661 8 73 600 371 374 417 150 629 520 236 625 508 168 733 36 282 427 121 534 715 558 187 707 714 368 882 437 607 27 18 15 988 306 198 130 343 70 42 248 257 714 3 133 859 658 52 385 487 572 25 211 485 381 453 198 496 576 7 18 89 103 218 494 679 981 133 59 69 73 397 517 567 542 8 619 13 247 373 355 745 81 291 401 142 357 244 7 581 440 6 963 173 750 763 1 382 278 5 275 103 7 843 2 14 86 374 97 218 15 319 55 503 886 44 27 228 375 796 430 146 873 39 5 714 366 732 679 369 642 344 978 237 230 98 273 98 58 850 266 608 739 2 190 592 194 84 611 14 101 909 4 582 122 12 122 994 635 916 0 89 10274 11922 300 6685 978 640 13718 132 143 7028 18239 1327 6881 2284 21156 2760 1998 5070 57 17805 2901 14519 1693 10841 11743 18976 9379 2092 285 3524 5983 16567 22972 1063 19938 131 4309 15177 40 21359 1207 2121 3421 233 27186 6872 310 11251 3786 1176 5352 4669 644 2427 1063 16 5886 1000 3615 18 918 12387 7059 4315 2057 15533 15664 1195 10141 8595 5218 6993 10755 19254 2432 9972 20357 3718 8450 3919 8454 5988 19 10140 12007 18903 3935 18739 11371 4330 3194 11908 1710 15085 1585 6893 5701 1207 2641 20082 1007 20670 242 16408 821 174 1941 6053 5509 10545 11073 13932 58 9389 3431 10249 5398 2521 19054 4835 829 4674 1201 126 2364 3885 858 5383 501 21304 4520 180 5604 9931 21101 168 19471 5338 712 5765 11653 9607 2457 18495 9954 105 11699 818 16356 3906 1654 10149 438 13133 7833 4447 5445 1326 10666 6309 4688 285 5169 40 1404 18295 3541 7125 8287 20290 8837 17858 1621 135 1115 1091 3288 54 2597 9955 16763 471 2335 1574 14642 16187 2376 1887 24636 5641 7433 17306 2957 6663 5966 3044 5358 9769 5905 611 17099 3300 11161 385 15895 19522 435 2108 3650 141 8058 21485 3988 2737 16273 4105 2571 11724 7296 1489 51 6519 5911 3647 2533 236 1190 4266 500 3338 7312 385 19463 4942 10835 11174 10700 9738 4477 16314 165 805 17700 4016 7057 12420 2756 17887 6796 5143 12927 6174 4740 20452 424 3101 11615 2445 13368 15983 15135 5582 12578 15525 4649 24252 6902 17168 460 228 413 23337 8237 3631 3838 6815 1706 1166 6713 5548 10910 65 1426 17897 8171 886 5466 8932 7274 277 2969 12341 10707 10334 2143 12639 7016 144 462 1829 1530 6394 14306 7206 16721 3469 1058 1201 1641 7989 7068 8612 8485 197 8113 306 6585 6213 4014 13889 2016 7397 6739 3985 10474 2701 107 8285 5588 90 10340 2717 16467 20426 22 9518 5965 124 6569 2065 136 23365 25 276 992 8245 1736 4797 316 6097 712 9186 25794 1282 431 3350 8782 9615 9031 3928 13928 394 118 18798 6870 18849 8115 10434 8884 3992 29004 6921 3450 2052 5705 2732 837 18597 6226 15329 13644 58 3923 10666 4191 1802 18180 242 2764 13987 101 10450 1509 311 1638 19358 11533 16943
示例输出 1
D R 1 R R 1 U 1 L 1 L 1 L R R R R R R R R 1 D 1 L 1 L 1 L 1 L 1 2 L 2 U 2 L 2 L L R R 1 R 1 D 1 L 1 L L 1 U