← 返回题目列表

AtCoder · ahc034_a

A. 用自卸车调平

中文机器翻译题面 查看原题

故事

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.

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 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