問題文
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 的答案 评分将通过在上面提交来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
- 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。
还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。