百度之星2008模拟题【三】简单印象

简单、可依赖是百度的性格，百度之星们又有怎样的性格呢？

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

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

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

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

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

输入样例
3 2 4
美丽 90 冷淡 -60 外向 -5 乐观 20
美丽 10 冷淡 20
外向 20 乐观 -5

输出样例
美丽 冷淡 外向

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

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

评分规则

1. 程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过2秒，否则该用例不得分；
   
2. 要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
   
3. 本题包含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分。注意：每个测试点的得分不一定为整数。