故事
AtCoder经常举办现场比赛,并决定建立自己的比赛场地。 规划建设地点位于山区,首先必须平整地面。 平整需要使用自卸卡车,这会产生装卸和运输土壤的费用。 确定以尽可能少的成本平整地面的方法。
问题陈述
有一个 N \times N 土地网格。 让 (0,0) 是左上角正方形的坐标, (i,j) 是所在正方形的坐标 i 向下平方并 j 方块。
高度 每个方格的 h_{i,j} 每个正方形的 (i,j) 作为输入给出。 所有正方形的总高度正好是 0.
最初,自卸车在广场 (0,0) 空载。 每回合中,您可以执行以下三种操作之一:
- 指定一个整数 d 满意 0<d\leq 10^6 加载 d 单位土从当前广场运到自卸车上。此操作将当前正方形的高度减小 d 并增加自卸车装载的土壤量 d。高度可以变为负值。此操作的成本为 d.
- 指定一个整数 d 满意 0<d\leq 10^6 卸载 d 单位土壤从自卸车到当前广场。此操作将当前正方形的高度增加 d 并减少自卸车上装载的土壤量 d。的价值 d 不得超过自卸车当前装载的土壤量。此操作的成本为 d.
- 将自卸车移动到相邻的方格(上、下、左或右)。自卸车不能移出规定范围 N \times N 网格。如果自卸车有 d 单位土壤装载,此操作产生的成本为 100+d.
您最多可以执行 100000 轮流操作。 您的任务是确定操作顺序,以最小化使每个正方形的高度的成本 0.
评分
让 \mathrm{cost} 是输出操作序列的总成本。 让 \mathrm{base} 是以下总和 |h_{i,j}| 对于所有人 (i,j)。 让 h_{i,j}' 是正方形的最终高度 (i,j)。 定义 \mathrm{diff} 作为总和 100|h_{i,j}'|+10000 对于所有人 (i,j) 这样 h_{i,j}' \neq 0。 然后,您将获得以下分数。
\[ \mathrm{round}\left(10^9\times \frac{\mathrm{base}}{\mathrm{cost}+\mathrm{diff}}\right) \]
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-1,0} \cdots h_{N-1,N-1}
在所有测试用例中, N 固定为 20。 初始高度 h_{i,j} 广场 (i,j) 是满足以下条件的整数 -100 \leq h_{i,j} \leq 100,所有高度的总和保证为 0.
输出
让 T 是操作圈数。 操作在 t- 第轮由字符串表示 s_t 如下:
- 加载操作 d 从当前方格到自卸车上的土壤单位:
+d - 卸载操作 d 从自卸车到当前方格的土壤单位:
-d - 将自卸车移至相邻方格的操作:
U,D,L,和R分别代表上、下、左、右。
然后,按以下格式输出到标准输出:
s_0
\vdots
s_{T-1}
输入生成
您不需要了解这一点。 我们建议更改 Web 可视化器中的种子值以观察生成的输入类型。
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 让 \mathrm{noise}(y,x,\mathrm{seed}) 是一个生成二维的函数 柏林噪音 缩放至以下范围 -1 和 1 基于随机种子值 \mathrm{seed}.
首先,生成 Perlin 噪声生成的种子值,如下所示 \mathrm{seed}=\mathrm{rand}(0,2^{32}-1).
接下来,对于每个 (i,j),生成 h_{i,j}=\mathrm{round}(\mathrm{noise}(i/10,j/10,\mathrm{seed})\times 50)。 如果 h_{i,j}=0 对于所有人 (i,j),然后重新生成 \mathrm{seed}.
让 S 是以下总和 h_{i,j}。 使 S=0,执行以下转换。
随机排列所有坐标 (0,0),(0,1),\cdots,(N-1,N-1) 以均匀随机的顺序,并让 k第坐标为 (i_k,j_k)。 如果 S>0,然后对于每个 k=0,1,\cdots,S-1,减少 h_{i_{k\% N^2},j_{k\% N^2}} by 1。 如果 S<0,然后对于每个 k=0,1,\cdots,-S-1,增加 h_{i_{k\% N^2},j_{k\% N^2}} by 1.
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
20 10 4 0 0 4 10 16 20 21 16 11 2 -7 -16 -23 -25 -23 -16 -7 2 16 10 6 5 7 10 13 15 14 10 4 -4 -13 -21 -29 -32 -29 -22 -13 -3 20 14 10 8 9 10 11 12 10 6 0 -7 -15 -24 -31 -33 -31 -25 -16 -8 20 15 12 10 10 10 10 11 8 5 0 -5 -12 -20 -26 -29 -28 -23 -15 -7 16 13 12 10 10 10 10 10 9 7 4 1 -4 -10 -16 -20 -20 -17 -10 -3 10 10 10 10 11 10 10 10 10 10 10 9 7 2 -3 -8 -9 -8 -3 3 4 7 9 10 10 10 10 10 11 14 16 18 17 14 9 5 1 1 4 9 0 5 8 10 10 10 10 10 12 15 20 24 25 24 19 14 9 7 9 13 0 6 10 12 11 11 9 9 10 14 20 26 29 28 24 18 13 10 10 14 4 10 14 16 13 10 7 5 6 10 16 23 26 26 23 16 10 8 6 10 11 16 20 21 16 10 4 0 0 4 10 16 21 20 16 10 4 0 1 4 16 23 26 24 18 9 1 -4 -7 -4 2 9 12 12 8 3 -3 -6 -7 -3 20 26 27 24 17 7 -3 -11 -14 -12 -7 -1 2 2 -1 -5 -10 -12 -11 -7 20 24 24 20 13 3 -8 -17 -21 -20 -16 -12 -9 -9 -11 -14 -15 -15 -12 -6 16 18 17 14 6 -3 -13 -20 -24 -25 -23 -21 -20 -19 -21 -21 -18 -15 -10 -3 10 10 8 4 -1 -8 -14 -20 -23 -25 -25 -26 -27 -28 -28 -25 -21 -14 -5 3 4 2 -1 -4 -7 -9 -12 -15 -18 -19 -23 -26 -29 -31 -31 -28 -21 -11 -1 8 0 -4 -7 -9 -9 -8 -7 -7 -8 -11 -16 -20 -26 -30 -31 -28 -20 -8 2 12 0 -6 -9 -10 -7 -3 1 3 3 -1 -7 -13 -20 -26 -29 -27 -20 -9 2 13 4 -3 -6 -6 -3 3 9 12 12 9 3 -5 -12 -20 -25 -26 -21 -12 -1 9
示例输出 1
+10 R +4 R R R R R R R +50 R R R R -7 D -13 L -44