← 返回题目列表

AtCoder · rco_contest_2017_final_b

B. 日本桥大渋滞

中文机器翻译题面 查看原题
<div class="part"> <部分> <h3>背景</h3> <p>嘟嘟——!</p> </部分> </div> <小时/>

問題文

H 行 W 有一个由列格组成的地图。其中 K 个格子上各有一辆车。

最上面的一行为 1 行,最左边的列 1 列,r 行 c 列的格子为 (r, c) 。

K 辆车各自的起始格子(称为原生格)和目的地格子(称为目标格)。车 i 少年格子是 (A_i, B_i) 。另外,车辆 i 的目标格是 (C_i, D_i) 。 您可以针对每辆车,在每个时刻 t (0 \leq t \lt L, t(为整数)指示向相邻格子移动。然后,在时刻 t+1 时,该车会到达指示的格子。但以下情况无法指示移动:

  • 如果在时刻 t 的目标格已有车辆存在
  • 同时多个车辆的移动目标格相同的情况
  • 移动目标在地图外的情况

在一次指令中,K 对所有车辆分别指示向相邻的四个方向移动,或者指示不移动,停留在当前格上。最多可发出 T 次指令。

每个测试用例的得分以及本问题的得分计算如下。

  • 在某个测试用例中的车辆 i 的最终位置是 (r_i, c_i) , 。
  • 指令数 L (0 \leq L \leq T) 作为 P_T = 10 + L \times 0.01 。
  • score = 10^7 / (P_D \times P_T)
  • 使用上述计算方法计算 score 四舍五入到最接近的整数是该测试用例的最终分数。
  • 总共有 30 个。每个测试案例的分数总和将作为这个问题的得分。

通过给出适当的指示来最大化您的分数。


入力

输入以下列格式从标准输入提供。输入均为整数。

H W K T
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_K B_K C_K D_K
  • H 是一个整数,表示地图中的行数,H=30 满足。
  • W 是一个整数,表示地图中的列数,W=30 满足。
  • K 是一个整数,表示地图上的汽车数量,K=450 满足。
  • T 是一个整数,表示可以向汽车发出的最大指令数,T=10,000 满足。
  • A_i 和 B_i 是一辆汽车 i 初始正方形 代表 (A_i, B_i) 的整数, 1 \leq A_i \leq H, 1 \leq B_i \leq W 满足。
  • C_i 和 D_i 是一辆汽车 i 目标方块 (C_i, D_i) 的整数, 1 \leq C_i \leq H, 1 \leq D_i \leq W 满足。
  • i \neq j 然后,(A_i, B_i) \neq (A_j, B_j) 和 (C_i, D_i) \neq (C_j, D_j) 满足。

出力

输出请按以下格式写入标准输出。

L
movement_0
movement_1
:
movement_{L-1}
  • 1 表示上线次数 L (0 \leq L \leq T) 输出。
  • t+2 (0 \leq t \lt L) 行显示时间。 一个字符串,表示t时向每辆车发出的指令 由movement_t输出。
  • movement_t (0 \leq t \lt L) 是 您也可以写 K 一串字符,movement_t 可以得到第 i 第一个字母是car 是时候发送至 i 代表 t 中的指令。
  • 每条指令由以下字符表示:
    U
    移动到比当前方格小一行的方格。 (向上移动)
    D
    移动到比当前方格大一行的方格。 (向下移动)
    L
    移动到比当前方格小一行的方格。 (向左移动)
    R
    移动到比当前方格大一行的方格。 (向右移动)
    -
    不移动。

关于测试案例的生成

每个测试用例都是使用以下步骤生成的。

  • 初始方格的候选者K正方形, 从H \times W方块中随机选择,确保没有重复项。
  • 随机选择那些初始正方形候选者。 分配给 K 辆车。
  • 成为目标方格的候选者K正方形, 从H \times W方块中随机选择,确保没有重复项。
  • 随机选择这些目标方格的候选者。 K 辆车。

入力例1

6 6 2 100
3 3 4 5
6 2 2 4

注意:这个输入不满足作为测试案例的条件。

汽车 1 的初始质量 1,1号车的目标方格 X,汽车2的初始质量 2,2号车的目标方格 带有 Y 的地图如下所示。

出力例1

4
RR
RU
DU
-L

执行完所有指令后,地图将如下所示: 1号车已到达目的地。

  • 時刻 0 然后车 1 和车 2 都向右移动。
  • 時刻 1 然后车 1 向右移动,车 2 向上移动。
  • 時刻 2 然后车厢 1 向下移动,车厢 2 向上移动。
  • 時刻 3 1 号车不动。 2号车向左移动。
  • 从该输出获得的分数计算如下。 自从我得到
    • 1号车的目标方格是 (4,5) 最终位置是 (4,5) 。
    • 2号车的目标方格是 (2,4) 最终位置是 (4,2) 。
    • 因此 连接 P_D 是 您也可以写 20+ (|4-4|+|5-5|)+(|2-4|+|4-2|)=24 。
    • P_T 是 您也可以写 10 + 4 \times 0.01=10.04 。
    • 此测试用例的分数是 10^7 / (24 \times 10.04) = 41500.6… 四舍五入 41501 。 对于

入力例2

30 30 450 10000
12 11 24 29
17 16 6 26
29 8 25 18
11 27 28 19
16 16 24 28
27 17 6 12
4 11 14 28
27 21 9 12
21 10 26 26
24 20 11 12
16 23 12 15
3 21 11 9
7 2 22 30
20 18 18 7
4 29 22 1
7 13 12 19
4 17 21 10
23 10 27 29
6 29 21 21
17 22 10 7
12 9 13 25
18 24 8 10
15 29 22 29
8 15 1 23
1 18 11 7
17 28 30 25
25 26 12 7
9 7 15 18
17 3 3 8
18 20 11 5
20 1 25 13
18 8 16 4
4 5 15 22
2 13 24 24
7 30 6 28
10 16 2 14
19 7 9 17
13 26 5 24
10 25 30 6
4 12 26 15
30 16 25 14
24 4 6 5
24 13 12 26
24 21 5 1
20 27 1 24
6 7 17 20
22 3 10 19
18 15 12 23
7 24 6 10
3 23 27 12
16 27 1 7
17 13 16 15
18 10 2 29
10 9 8 27
9 1 19 29
16 13 17 6
25 16 7 1
18 6 12 17
26 14 20 16
2 9 9 13
22 2 16 16
12 28 15 17
11 5 25 2
11 29 8 21
25 9 17 27
5 19 4 9
13 29 22 25
30 28 11 20
9 5 1 2
6 11 21 30
22 13 22 20
6 28 19 6
11 24 5 15
29 24 5 14
21 29 25 10
18 21 14 6
2 8 17 30
6 16 26 8
9 30 11 26
11 7 20 23
18 19 6 6
16 4 27 4
7 22 8 28
2 4 5 6
30 20 4 11
15 5 9 18
12 21 30 23
20 25 18 14
8 11 9 28
8 17 26 11
30 9 30 29
14 11 24 15
17 6 4 17
4 23 14 26
18 7 14 12
29 10 9 22
20 22 17 18
26 23 17 8
23 16 7 16
3 16 22 28
16 15 27 19
8 3 29 2
28 21 16 5
19 19 13 17
2 30 12 25
28 23 13 16
6 24 6 19
8 22 24 22
20 29 10 16
7 26 27 9
1 21 2 24
25 30 1 30
17 23 28 16
10 13 23 29
19 14 25 11
16 11 6 29
13 2 4 1
20 4 9 27
11 15 2 15
22 26 10 23
23 7 11 1
6 17 3 2
18 14 16 13
24 28 1 13
8 30 26 29
9 24 8 7
21 30 25 26
26 11 9 29
21 14 30 8
28 17 28 12
3 5 28 13
21 22 21 7
30 13 24 6
24 10 15 4
28 16 5 18
24 11 18 24
24 12 1 17
20 11 3 7
30 29 17 17
12 5 19 10
19 24 30 27
29 3 1 10
4 3 21 22
15 16 17 16
1 28 6 4
30 6 23 14
12 26 4 23
6 25 23 12
4 26 25 9
13 22 29 16
19 20 6 22
4 14 12 4
17 14 4 12
13 7 20 8
29 12 15 27
2 25 22 6
12 3 28 3
7 18 19 20
18 9 13 24
10 11 8 19
29 25 9 4
11 3 20 28
14 24 11 23
19 8 25 6
14 10 1 29
9 29 28 4
16 5 27 3
10 12 2 9
9 19 7 23
15 18 10 1
6 27 13 21
4 30 30 2
1 1 28 5
24 2 14 15
29 19 12 3
12 22 14 14
25 28 9 30
15 8 11 11
15 14 19 11
19 10 29 26
21 21 2 22
24 1 11 28
30 30 8 1
28 5 26 3
4 8 19 27
6 30 11 3
19 15 22 5
16 28 5 29
2 5 23 9
26 25 25 19
17 5 7 22
18 1 3 19
28 14 6 1
10 21 8 13
14 28 18 26
9 8 16 24
11 25 4 4
28 11 24 13
30 3 24 9
3 9 6 30
16 20 3 3
11 9 23 4
15 6 12 16
13 23 12 24
25 19 28 1
5 24 27 28
28 10 26 25
27 20 15 2
17 20 21 14
3 6 19 3
17 11 21 6
1 29 2 4
25 17 29 15
22 24 12 30
22 27 6 23
6 19 30 19
13 16 30 28
14 1 6 18
27 16 6 3
8 26 9 26
18 4 23 13
16 30 14 1
20 6 10 6
12 24 3 10
19 1 24 16
5 11 7 2
2 20 29 8
18 2 16 1
4 24 22 8
17 8 27 16
19 22 24 27
22 28 9 23
1 10 12 10
12 4 3 13
8 1 11 24
3 7 13 9
21 3 1 12
30 1 26 6
1 16 13 8
10 17 24 20
6 9 5 21
22 21 5 5
10 20 16 27
5 18 18 16
16 12 23 26
25 22 12 6
29 27 6 17
15 19 23 30
2 3 25 27
5 28 8 3
15 20 12 9
15 4 25 7
9 12 7 4
24 30 25 4
20 5 3 5
6 2 20 25
15 23 23 28
26 26 7 25
23 27 27 2
5 27 30 12
21 1 26 13
23 24 10 11
5 29 3 6
2 19 5 11
22 7 5 19
20 17 27 26
14 23 25 22
21 15 19 30
28 19 1 27
27 30 25 5
23 17 14 7
27 5 17 2
26 30 29 5
7 12 14 21
9 3 15 3
8 24 19 28
3 3 7 11
2 26 10 26
30 10 21 11
1 3 22 23
10 28 2 7
19 27 14 24
28 24 30 13
21 9 14 2
15 28 2 23
5 6 10 13
27 18 16 2
17 18 10 28
19 11 20 26
13 11 16 21
15 25 24 3
3 24 22 24
1 8 11 15
15 15 23 2
26 15 29 1
1 14 20 15
28 1 4 20
7 10 3 11
14 5 25 1
29 11 13 26
25 29 8 5
18 27 17 3
22 14 25 16
17 7 19 8
25 23 30 1
23 23 12 13
26 24 10 17
8 4 12 8
17 30 7 24
29 2 20 10
7 1 3 23
26 9 29 23
23 15 30 7
27 9 15 21
25 4 1 25
8 14 23 17
23 12 19 7
13 27 27 14
5 15 27 17
16 22 10 21
1 4 3 27
12 29 21 2
24 15 29 17
21 8 23 18
12 17 30 18
28 20 11 17
23 18 21 27
13 5 5 4
14 2 6 24
1 12 28 10
14 27 18 25
27 4 30 26
16 2 7 28
5 20 28 8
3 17 20 9
1 25 21 16
26 19 11 30
4 20 25 8
10 15 20 17
6 5 19 26
20 14 24 5
1 7 21 9
13 15 30 15
23 2 7 8
15 1 1 18
19 17 10 18
16 10 21 15
23 21 6 14
8 25 1 1
21 18 13 18
9 4 24 11
18 28 17 1
27 3 25 24
20 9 10 15
30 11 13 11
13 28 29 14
17 25 23 1
15 12 16 10
19 18 13 23
1 19 2 6
8 7 8 30
22 12 6 7
8 2 16 9
17 26 7 26
3 30 14 19
4 4 28 27
13 12 20 1
9 6 15 13
24 24 2 28
21 20 26 17
29 29 25 28
23 28 30 9
16 21 29 18
22 15 27 27
5 12 20 13
26 7 11 8
12 7 13 2
16 25 15 9
20 20 13 6
16 3 21 17
8 27 17 11
18 12 12 5
4 18 9 2
1 2 28 30
15 17 18 6
17 24 26 5
16 9 20 12
30 14 22 4
19 5 21 8
12 15 9 10
6 8 2 20
25 2 6 27
30 7 13 5
6 26 16 29
10 30 7 12
9 28 23 16
3 13 30 11
27 19 30 17
1 5 9 16
10 3 14 11
19 30 8 4
3 10 2 21
1 15 8 16
29 4 18 13
6 12 28 15
7 27 24 26
26 10 7 6
12 8 14 4
4 16 5 2
13 18 21 19
26 18 3 16
24 7 6 20
3 15 19 23
20 16 19 16
14 6 27 30
13 30 1 28
14 30 20 11
23 29 8 11
9 2 1 5
27 25 30 4
18 3 22 9
8 10 21 4
7 20 30 22
14 20 16 20
22 29 5 20
24 19 12 20
28 13 11 16
21 7 12 29
21 5 14 8
12 19 1 3
10 4 15 23
2 11 14 18
25 25 15 28
22 9 13 30
27 6 9 15
15 13 25 30
25 13 16 23
7 29 10 10
17 9 28 23
11 1 19 14
21 13 12 18
27 2 6 21
20 30 23 21
11 14 20 7
26 8 4 28
5 16 15 25
18 26 7 19
22 1 19 19
20 12 4 8
7 7 3 14

到发电机 通过指定 seed=1 可以获得相同的输入。

出力例2

2
RRUL---UD--DR-LR---DD--RD-UD--R-D--UDLL-LRR-L-RR-LLDRRD-L---ULUL-U-U-D--LL---L-RLDRDL-DLDDU-UD---LU-D-RD-ULDU-R-DRLUUU-LLU-LLL-R----ULLUD--RRUD-DULDLDRD--UDDD-D-RRDU---UD-DDRL--RDDU-UL--DRR--UUU-R-URDL-RR-R-U-D-DRUUDRULDRU-LRLDU--RUD--RURDDRLDD-UU--------RRDLL---DRD-R-LUULD--LD--LL---D-RR---R-RDULL-UUD--LURLUU--RRD---U--R---ULRLD-LD-L---DLDDRRU-L----UUR-----RL--LDDDRLU-D-RU-L---U-DD--URLURU-LLD-R-URDRR-UD-DLRDURULR-DDLRURUU-RL-R--U-RLRD-U-LU-LD-R
DRU-DLDU-LUDRLLR-DDU-D-UL--D-L--DD--U-DDUURULDR-ULU-RURD--R-RL-L-D-L-D--LLD--LDD--DDLRR-DDD-R---U---D-LUDULDL-D--DR-UU-LUD-UR--RDLDLUU-DRULD-U--DUL--L-------DR-RRL-U-L-RU--DRLLRUUD-RLD--L-DLR--LLDURRR-DR--DRU-D--DRLUDR---U---LUUD-DUDRDRRR--RUDD--L-RL----U--UL-DL-LD--U-L--LR-DDD--LRDU-DD---D-RD-DRR-RL---LUUR--RD-URRUL-LRLD--U---DDRUD-L-DR--DLRU-R---ULRRL---LL-U--DDRD-DL----U--U-L-D-ULDU-L-RU-LR--RDU-DUD-RD-RU---LU-L----DD-----U-DR-R--D-U-ULL-DRR-U

发生器和测试仪

发电机和测试器可从以下链接提供。

发电机测试仪


展示台

我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。

  • 此可视化工具已经过测试,可在主要浏览器上运行,但不能保证在所有环境中都能运行。
  • 此可视化工具上计算的分数不是本次比赛的分数。 AtCoder 的答案 评分将通过在上面提交来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台

观察仪主体