首先...我偷懒了。下面2题为百度之星2007复赛题。略有修改。

================================================================
[b]A 简单印象[/b]
================================================================
[img]http://star.baidu.com/data/fusai/f1q3.jpg[/img]
简单、可依赖是百度的性格，百度之星们又有怎样的性格呢？

有n名选手入围了百度之星程序设计大赛的复赛阶段。为了让选手相互之间有更多的了解和更好的交流，组委会工作人员邀请每位选手选择一些不同的词语来介绍自己的性格。每名选手需要为自己选定的每一个词语指定一个绝对值不超过100的整数权值q，表示这个词语在多大程度上描述了自己的性格。例如“美丽 90”表示该选手认为自己非常美丽，“冷淡 -60”表示比较热情，而“外向 -5”表示稍微有一点点偏内向。你不需要考虑词语本身的语义，比如“外向 -5”不代表“内向 5”。

组委会发现不少选手的性格都有相似之处，所以希望找到一组词语尽量准确的描述所有的选手。对于选出的词语集合S，定义选手i被描述的精确程度P(i)为S中所有词语在选手i眼中的权值之和（选手i没有提到的词权值视为0），组委会希望让最小的P(i)尽量大，因为这样才能让选出的词语能够描述所有选手，而不仅仅是部分。

另外，所选词语的个数也是有讲究的。词语太少会略显单薄，而词语太多又不方便宣传，所以组委会设定了词语个数的最小值min和最大值max。


[b]输入数据[/b]
输入数据第一行为三个非负整数n, min和max，表示选手的个数、词语数的最小值和最大值，接下来的n行，每行包括若干“词语-权值”对（用空格隔开）。词语保证由不超过10个汉字组成（用GBK编码，不含非汉字），权值为绝对值不超过100的整数。 

[b]输出数据[/b]
仅一行，输出各个词语，用空格隔开。词语总数必须不小于min且不大于max，每个词语都必须至少被一个选手提到过，否则视为非法输出。你的输出不必是最优的，只要输出合法，就能得到一定的分数。 

[b]输入样例[/b] [url=http://star.baidu.com/data/fusai/f1q3.d1.in.txt]例[/url]
3 2 4
美丽 90 冷淡 -60 外向 -5 乐观 20
美丽 10 冷淡 20
外向 20 乐观 -5


[b]输出样例[/b] [url=http://star.baidu.com/data/fusai/f1q3.d1.out.txt]例[/url]
美丽 冷淡 外向


[b]样例解释[/b]
如果把选手按照输入中出现的顺序编号为1~3，则P(1)=90-60-5=25，P(2)=10+20=30，P(3)=20，所有P中的最小值为20。 

[b]注意事项[/b]
输入数据的中文采用GBK编码。
GBK：是又一个汉字编码标准，全称《汉字内码扩展规范》。采用双字节表示，总体编码范围为 8140-FEFE，首字节在 81-FE 之间，尾字节在 40-FE 之间，排除xx7F。总计 23940 个码位，共收入 21886 个汉字和图形符号，其中汉字（包括部首和构件）21003 个，图形符号 883 个。

[b]评分规则[/b]

内存使用不作严格限制在每一测试用例上运行不能超过2秒，否则该用例不得分；

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

本题包含30个测试点，每个测试点10分，共300分。
测试点1~10满足n<=100, 1<=min<=max<=5, 涉及到的词语不超过500个。
测试点11~20满足n<=200, 10<=min<=max<=15, 涉及到的词语不超过2000个。
测试点21~30满足n<=400, 25<=min<=max<=30, 涉及到的词语不超过10000个。
每个测试点独立评分。对于每个测试点，你的得分不仅取决于你的输出，还取决于其他选手的输出。非法输出的得分为0，合法输出的得分大于0。设合法输出的程序数为M，比程序i的方案严格更优的程序数为Y(i)，则该测试点程序i的分值为10(1-Y(i)/M)。换句话说，输出该测试点最优解的程序将获得10分，而最差解惟一的情况，输出最差解（但合法）的选手将得到10/M分。注意：每个测试点的得分不一定为整数。

================================================================
[b]B 紧急修复[/b]
================================================================
[img]http://star.baidu.com/data/fusai/f1q4.jpg[/img]

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


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

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

[b]输入格式[/b]
输入的第一行为三个正整数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。


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


[b]输入样例[/b] [url=http://star.baidu.com/data/fusai/f1q4.d1.in.txt]例[/url]
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


[b]输出样例[/b] [url=http://star.baidu.com/data/fusai/f1q4.d1.out.txt]例[/url]
MOVE U
MOVE RRRD
MOVE RDRURD
REPAIR
MOVE DRRU
MOVE DRRRU
REPAIR
REPAIR
REPAIR
REPAIR
MOVE DRUL
REPAIR
SLEEP
REPAIR
REST


[b]模拟器[/b]

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


模拟器用python编写，没有安装python的选手可以在http://www.python.org/下载[url=http://www.python.org/ftp/python/2.5.1/python-2.5.1.msi]最新版本[/url]。


[b]评分规则[/b]

内存使用不作严格限制，在每一测试用例上运行不能超过2秒，否则该用例不得分；

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

本题包含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分。注意：每个测试点的得分不一定为整数。

附baidu提供的模拟器代码(如果上面提供的模拟器链接失效的话)
[code=c]
#
# Simulator for BaiduStar 2007, Round 2, Problem 4
#
# Usage: judge.py <input file> <output file>
#
# Note:
# 1. Please ensure that input file is correct
# 2. The internal coordinates start from 0, not 1
#

import sys

def readlist(f):
  """ read a line as an integer list """
  return [int(x) for x in f.readline().split()]

def readinput(infile):
  """ read input data """
  global R, C, T, k, n, city, company, team, idx
  try:
    f = open(infile, 'r')
    R, C, T = [int(x) for x in f.readline().split()]

    # the city map
    city = []                    
    for i in range(R):
      city.append(f.readline())
        
    # (r, c, B, P)  
    company = []
    idx = {}
    k = int(f.readline())
    for i in range(k):
      l = readlist(f)
      l[0], l[1] = l[0] - 1, l[1] - 1
      idx[(l[0], l[1])] = i # coordinate => company_index mapping
      company.append(l)

    # (r, c, s)      
    team = []
    n = int(f.readline())
    for i in range(n):
      l = readlist(f)
      l[0], l[1] = l[0] - 1, l[1] - 1
      team.append(l)
      
  except:
    sys.stderr.write('Error processing input file')
    sys.exit()
    
  finally:
    f.close()

def readoutput(outfile):
  """ read user output """
  global cmd
  try:
    f = open(outfile, 'r')
    cmd = []
    for i in range(n*T): cmd.append(f.readline().split())
  except:
    sys.stderr.write('Error processing output file')
    sys.exit()
  finally:
    f.close()

def move_team(i, direction):
  """ move the i-th team in a direction """
  dr = {'U':-1, 'D':1, 'L':0, 'R':0}
  dc = {'U':0, 'D':0, 'L':-1, 'R':1}
  r, c = team[i][0] + dr[direction], team[i][1] + dc[direction]
  if r < 0 or r > R-1 or c < 0 or c > C-1:
    return 'moving out of the map'
  if city[r][c] == '#':
    return 'moving into an obstacle'
  if city[team[i][0]][team[i][1]] == 'O' and city[r][c] == 'O':
    return 'moving from building to building directly'
  team[i][0], team[i][1] = r, c
  return 'ok'

def simulate():
  """ Do the simulation """  
  global cost
  cost = 0
  for hour in range(T):
    print '*** Hour %d ***' % (hour+1)
    
    # step 1: process companies
    for i, c in enumerate(company):
      print 'Company %d: Location = (%d,%d)' % ((i+1), (c[0]+1), (c[1]+1)),
      if c[2] > 0:
        print 'B = %d, Lost $%d' % (c[2], c[3])
        cost += c[3]
      else:
        print 'repaired'
        
    # step 2: process commands
    for i, t in enumerate(team):
      print 'Team %d:' % (i+1),
      c = cmd[hour*n+i]
      
      if c[0] == 'MOVE':
        seq = c[1]
        print 'Moving (%d,%d)' % ((t[0]+1), (t[1]+1)),
        for j, direction in enumerate(seq):
          if j == t[2]:
            print
            print 'Warning: sequence too long.'
            break
          msg = move_team(i, direction)
          if msg == 'ok':
            print '-> (%d,%d)' % ((t[0]+1), (t[1]+1)),            
          else:
            print
            print 'Warning: cannot move %s(%s), rest part of the sequence is ignored.' % (direction, msg)
            break
        else:
          print
          
      elif c[0] == 'REPAIR':
        print 'Repairing',
        coord = (t[0], t[1])
        if coord in idx.keys():
          comp = company[idx[coord]]
          print 'company %d' % (idx[coord]+1)
          if comp[2] == 0:
            print 'Warning: company already repaired'
          else:
             comp[2] -= 1;
        else:
          print
          print 'Warning: No company at (%d,%d)' % ((t[0]+1), (t[1]+1))
          
      elif c[0] == 'REST':
        print 'Resting'
        
      else:
        print '???'
        print 'Warning: illegal command: ', c[0]

    # print an empty line    
    print

# main program
if len(sys.argv) != 3:
  print 'Usage: judge.py <input file> <output file>'
  sys.exit()

infile = sys.argv[1]
outfile = sys.argv[2]

print 'Processing input file:', infile
readinput(infile)
print 'Processing output file:', outfile
readoutput(outfile)

print
simulate()
print 'Cost = ', cost
[/code]