百度之星2008模拟题【四】紧急修复

2050年的一天，某市k家公司的计算机系统突然同时瘫痪。市政府很快找到了问题的所在，并开始研发一套自动修复系统。该系统启用后整个城市的计算机系统将恢复正常，但由于研发时间较长，在此之前各公司仍将蒙受不小的损失。为此，市政府决定派出n支维修能力相同的维修队到各公司进行手工修复，力图在系统启用前将整个城市的总损失降低到最小限度。

城市被划分成R*C的网格，各行从上到下编号为1~R，各列从左到右编号为1~C。每个格子为空地、障碍物和建筑物之一（公司总是位于某个建筑物格子中，且不同的公司总是在不同的建筑物格中）。维修队每次只能往上（行编号减1）、下（行编号加1）、左（列编号减1）、右（列编号加1）四个方向移动，第i支维修队每个小时可以移动s(i)格。维修队在任何时候都不能位于障碍物中，但建筑物可以从它上下左右的相邻空地进入，也可以从这些格子出去。注意：不能直接从一个建筑物格移动到另一个建筑物格，而必须先移动到相邻的空地，在空地上移动，然后再进入另一个建筑物。每个格子的实际尺寸很大，因此可以有多个维修队同时在同一个格子中。第i家公司的位置为(r(i), c(i))，瘫痪程度为B(i)，每小时的经济损失为P(i)元。瘫痪程度的单位是“队·小时”，即一支维修队每小时可以把一个公司的瘫痪程度降低1，而如果m支维修队同时为一个公司修复，每小时可以把该公司的瘫痪程度降低m。注意，在完全修复之前，每个小时的经济损失不变。

政府的修复计划应包含每个小时各维修队所执行的命令。这些命令包括：

1. REST
该命令不进行任何操作。

2. MOVE
按照seq进行移动。其中seq为一个长度不超过s(i)的非空字符串（如果不需要移动，请使用REST命令）。如果seq的长度超过s(i)，则从第s(i)+1个字符开始的剩余部分将被删除；如果该命令不能完全成功的执行，则从第一个非法移动开始的所有后续移动将被忽略。 seq的取值范围为：U,D,L,R。分别表示上、下、左、右。字符区分大小写, 其他字符视为非法。

3. REPAIR
对当前公司进行维修。如果当前公司已经修复或者该维修队的当前位置不是公司，该命令将被忽略。该命令后面加的所有参数将被忽略。

需要特别注意的是，每个小时只能执行一条指令，例如不能在MOVE之后立刻REPAIR，必须等待下一个小时。

输入格式
输入的第一行为三个正整数R, C, T即网格的行数、列数和自动修复系统的启用时间。以下R行每行C个字符，表示该城市的地图。点表示空地，#表示障碍物，O表示建筑物。 下一行包含一个正整数k，表示公司的数目。以下k行每行四个整数r, c, B, P，其中(r,c)表示该公司坐标(1<=r<=R, 1<=c<=C)，B为该公司的初始瘫痪程度，P为每小时的经济损失。(r,c)处保证为一个建筑物格。B和P均为正整数，且P不超过200。 下一行包含一个正整数n，表示维修队的个数。以下n行每行包含三个整数r, c, s，(r,c)表示该维修队的初始位置, s表示它每小时最多移动的格子数。维修队按照输入文件中的顺序编号为1~n。

输出格式
输出每n行为一组，描述一个小时各维修队的发出的命令。共T组，一共n*T行。所有格式非法的指令将被忽略（等效于REST）。尽管如此，如果程序输出不足n*T行，或者命令中没有REPAIR，或者所有的REPAIR都没有成功执行，则输出将视为非法。你的程序不必输出最优解，任何一个合法解都将得到一定的分数。

输入样例
4 7 5
...#OO#
#.....#
O...##O
#......
2
1 5 1 5
3 7 4 6
3
4 7 5
1 1 5
3 1 5

输出样例
MOVE U
MOVE RRRD
MOVE RDRURD
REPAIR
MOVE DRRU
MOVE DRRRU
REPAIR
REPAIR
REPAIR
REPAIR
MOVE DRUL
REPAIR
SLEEP
REPAIR
REST

模拟器

为了更清晰的说明规则并帮助选手设计和测试程序，命题组开发了一个简单的。该模拟器根据输入数据和程序输出进行模拟，并给出详细过程和最后的结果。最终的测试将严格按照该脚本的输出进行评判。你可以用它测试样例输入和输出，或者自己设计的其他数据。模拟器将会对各条非法指令给出警告信息(例如非法的移动,无法识别的指令等)。
每小时的模拟过程如下：
第一步：对于每个尚未修复的公司i，将P(i)累加进总损失。
第二步：按照序列从小到大的顺序依次执行各维修队的指令。

模拟器用python编写，没有安装python的选手可以在下载。

评分规则

1. 程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过2秒，否则该用例不得分；
   
2. 要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
   
3. 本题包含30个测试点，每个测试点10分，共300分。
   测试点1~10满足R, C<=10, n<=5, k<=10, B<=15, T<=30
   测试点11~20满足R, C<=30, n<=10, k<=20, B<=50, T<=500
   测试点21~30满足R, C<=100, n<=100, k<=500, B<=1000, T<=10000
   每个测试点独立评分。对于每个测试点，你的得分不仅取决于你的输出，还取决于其他选手的输出。非法输出的得分为0，合法输出的得分大于0。设合法输出的程序数为M，比程序i的方案严格更优的程序数为Y(i)，则该测试点程序i的分值为10(1-Y(i)/M)。换句话说，输出该测试点最优解的程序将获得10分，而最差解惟一的情况，输出最差解（但合法）的选手将得到10/M分。注意：每个测试点的得分不一定为整数。