1.百度语言翻译机
百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套独特的缩略语。他们在平时的交谈、会议，甚至在各种技术文档中都会大量运用。
为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩略语和专有名词翻译成日常语言。
输入要求：
输入数据包含三部分：
1. 第一行包含一个整数N(N<=10000)，表示总共有多少个缩略语的词条；
2. 紧接着有N行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩略语（仅包含大写英文字符，长度不超过10字节），第二个字符串为日常语言（不包含空格，长度不超过255字节）；
3. 从第N+2开始到输入结束为包含缩略语的相关文档（总长度不超过1000000个字节）。例：
6
PS 门户搜索部
NLP 自然语言处理
PM 产品市场部
HR 人力资源部
PMD 产品推广部
MD 市场发展部
百度的部门包括PS，PM，HR，PMD，MD等等，其中PS还包括NLP小组。
样例：in.txt
输出要求：
输出将缩略语转换成日常语言后的文档。（将缩略语转换成日常语言，其他字符保留原样）。例：
百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。
样例：out.txt
2.饭团的烦恼
“午餐饭团”是百度内部参与人数最多的民间组织。
同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们增进感情。
但是，随着百度的员工越来越多，各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃，饭团的点菜负责人的压力也越来越大。现在，这个任务就交给“百度之星”了，因为，你将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下：
1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近12元越好。
2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
3．请谨记，百度饭团在各大餐馆享受8折优惠。
输入要求：
1．输入数据第一行包含三个整数N，M，K(0<N<=16，0<M<=N，0<K<=12)，分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数；
2．紧接着N行，每行的格式如下：
菜名（长度不超过20个字符） 价格（原价，整数）是否荤菜（1表示是，0表示否） 是否辛辣（1表示是，0表示否）；
3．第N+2行是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。例：
3 2 2
水煮鱼 30 1 1
口水鸡 18 1 1
清炖豆腐 12 0 0
1 1 1 1
样例：in.txt
输出要求：
对于每组测试数据，输出数据包含M+1行，前M行每行包含一个菜名（按菜名在原菜单的顺序排序）。第M+1行是人均消费，结果保留两位小数。例：
口水鸡
清炖豆腐
12.00
样例：out.txt
3.变态比赛规则
为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。
由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。
比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。而如果是1，2，3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4，2 vs 4，3 vs 4。
很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。
相信作为编程高手的你一定知道该怎么回答这个问题了吧？那么现在请你帮助W.Z吧。
输入要求：
每行为一组数据，包含两个数字 N, K(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2
样例：in.txt
输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
样例：out.txt
4.蝈蝈计分
蝈蝈小朋友刚刚学会了0~9这十个数字,也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“3 2 4”可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用0~9这十个数字，所以当比赛选手得分超过9的时候，他会用一个X来表示10完成记分。但问题是，当记录为“X 3 5”的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。
因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢～于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛过程的情况，也要输出相应的提示哦。
需要进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获胜三局后就获得最终胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。
输入要求：
1．文件中第一行只有一个整数M，表示蝈蝈记录了多少场比赛的分数；
2．在接下来的2M行里，每场比赛用两行记录，第一行是一个整数N(N<=1000)表示当前这个记录中有多少个字符，第二行就是具体的N个字符表示记录的分数（相邻字符用空格隔开）。例：
3
23
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1
25
9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4
43
7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1
样例：in.txt
输出要求：
对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用":"分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测，以“UNKNOWN”一个单词独占一行表示（请全部使用大写字母）。例：
21:17
24:22
21:3
UNKNOWN
21:14
20:22
21:23
21:16
21:9
样例：out.txt
5.座位调整
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，效率会大大提高。因此，百度决定进行一次员工座位的大调整。
调整的方法如下：
1．首先将办公区按照各种零食的摆放分成N个不同的区域（例如：可乐区，饼干区，牛奶区等等）；
2．每个员工对不同的零食区域有不同的喜好程度（喜好程度是1~100的整数，喜好程度越大表示该员工越希望被调整到相应的零食区域）；
3．由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。
输入要求：
文件第一行包含两个整数N，M(N>=1，M<=300)。分别表示N个区域和M个员工；
第二行是N个整数构成的数列a，其中a[i]表示第i个区域可以容纳的员工数(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；
紧接着是一个M*N的矩阵P，P(i,j)表示第i个员工对第j个区域的喜好程度。例：
3 3
1 1 1
100 50 25
100 50 25
100 50 25
样例：in.txt
输出要求：
对于每个测试数据，输出可以达到的最大的喜好程度。例：
175
样例：out.txt
数据解释：
此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175
6.剪刀石头布
N个小孩正在和你玩一种剪刀石头布游戏（剪刀赢布，布赢石头，石头赢剪刀）。N个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩M次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在M次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。
输入要求：
输入文件包含多组测试数据，每组测试数据第一行为两个整数N和M(1<=N<=500，0<M<=2000)，分别为小孩的个数和剪刀石头布游戏进行的次数。接下来M行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号（为小于N的非负整数）。符号的可能值为“=”、“>”和“<”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
样例：in.txt
输出要求：
1．每组测试数据输出一行，若能猜出谁是裁判，则输出裁判的编号，并输出在第几次游戏结束后就能够确定谁是裁判，小孩的编号和游戏次数以一个空格隔开；
2．如果无法确定谁是裁判，输出-2；如果发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出-1。例：
-2
1 4
-1
0 0
程序之美”-百度之星程序设计大赛 - 题目
第一题（共四题100分）：连续正整数（10分）
题目描述：
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
输入数据：
一个正整数，以命令行参数的形式提供给程序。
输出数据：
在
标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序
列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。
例如，对于15，其输出结果是：
1 2 3 4 5
4 5 6
7 8
对于16，其输出结果是：
NONE
评分标准：
程序输出结果是否正确。
第二题（共四题100分）：重叠区间大小（20分）
题目描述：
请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为[10 12]，其大小为3；行(20 10)和（20 30）的重叠区间大小为1。
输入数据：
程
序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有用一个空格分隔的2个正整数，这2个正整数的
大小次序随机，每个数都在1和2^32-1之间。（为便于调试，您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：
在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。
评分标准：
程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。
第三题（共四题100分）：字符串替换（30分）
题目描述：
请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。
输入数据：
程
序读入已被命名为text.txt和dict.txt的两个输入数据文本文件，text.txt为一个包含大量字符串（含中文）的文本，以
whitespace为分隔符；dict.txt为表示字符串（s1）与字符串（s2）的对应关系的另一个文本（含中文），大约在1万行左右，每行两个字
符串（即s1和s2），用一个\t或空格分隔。dict.txt中各行的s1没有排序，并有可能有重复，这时以最后出现的那次s1所对应的s2为准。
text.txt和dict.txt中的每个字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必须和dict.txt
中的某s1完全匹配才能被替换。（为便于调试，您可下载测试text.txt和dict.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：
在标准输出上打印text.txt被dict.txt替换后了的整个文本。
评分标准：
程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。
第四题（共四题100分）：低频词过滤（40分）
题目描述：
请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数，则将这些单词都删除。
输入数据：
程序读入已被命名为corpus.txt的一个大数据量的文本文件，该文件包含英文单词和中文单词，词与词之间以一个或多个whitespace分隔。（为便于调试，您可下载测试corpus.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：
在标准输出上打印删除了corpus.txt中出现次数最少的单词之后的文本（词与词保持原来的顺序，仍以空格分隔）。
评分标准：
程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。
第一题（共两题100分）站点统计（50分）
题目描述：
一个Internet站点集合，可以用如下的方式来描述站点和站点之间的链接引用关系：
s 1 2 3 4
1 / 4 0 3
2 3 / 4 5
3 2 2 / 2
4 6 1 4 /
其中与s(site)同行和同列的数字都表示站点号，其他每个数字表示一个站点到另一个站
点的超文本链接数。如果站点A有到另一个站点B的直接链接或间接（指通过一个或多个
直接链接）链接，则称站点A有到站点B的访问关系，或称站点B可以被站点A访问到。例
如，上面描述了一个有4个站点链接关系的站点集合，第一行 / 4 0 3 表示站点1到站点
1，2，3，4的超文本链接数。
请编写程序:
1） 将一个有N个站点的集合划分成满足下面所有条件的站点子集（这些子集的union组
成了该N个站点集合）：
a) 当任一子集中的站点数大于1时，该子集内至少存在一个站点有到该子集内所有
其他站点的访问关系；
b) 当任一子集中的站点数大于1时，该子集内的任一站点至少可以被该子集内的某
一站点访问到；
c) 两个不同子集中的任意两个站点之间不存在任何访问关系。
2） 裁减这些子集内的站点之间现有的链接关系，使得被裁减后的各子集内的站点依然
可以满足上述所有条件，同时使得子集内的站点之间的链接总数相加之和为最小。
假如上面的站点集合是这N个站点集合中的一个子集，它满足了条件a)：4可以访问到3，
也可以访问到2和1；也满足了条件b)：站点4可以被站点3访问到，等等。对该站点集合
进行裁减使其仍然满足条件a和b，并使得其链接总数之和为最小的结果为：
s 1 2 3 4
1 / 0 0 0
2 0 / 0 0
3 2 0 / 2
4 0 1 4 /
这里，站点4可以访问到站点3和2，站点4也可以访问到站点1（通过站点3间接访问）；
此外，站点3可以访问到站点4；最小链接总数相加为2＋2＋1＋4=9。
输入数据：
程序读入已被命名为sites.txt的完全如上所示的N*N矩阵的输入数据文本文件，N不大于
10万（N即为行数和列数），输入文件的每一行的列和列之间用一个\\t分隔，行和行之
间用\\n分隔。
输出数据：
按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和，数和数
之间都以一个空格分隔。如上述子集和最小链接总数为：
1 2 3 4 9
如果输入数据无满足题目要求的子集存在，则输出NONE。
评分标准：
在结果正确的前提下，会考虑程序的运行时间。我们会用两个不同的输入数据文件（一
个简单一个复杂）进行测试，简单的输入数据产生的程序输出结果如果正确，获该题满
分的30%即15分（不处理运行时间，除非因程序错误引起的超时运行）；复杂的输入数据
产生的程序输出结果如果正确，获50%即25分，运行时间满分为20%即10分，按各自程序
的运行时间在所有参赛选手的程序的运行时间中所占位置获得相应比例。请仔细阅读并
遵守"输入数据"和"输出数据"中的格式要求，如不符合要求，我们的自动评分程序可能
会判定程序不正确。
第二题（共两题100分）决策系统（50分）
题目描述：
一个智能决策系统可以由规则库和事实库两部分组成，假定规则库的形式为：
Ri C1 & C2 & … & Cn->A
表示在条件C1，C2，… 和Cn都满足的前提下，结论A成立（即采取行动A）；Ri表示这是
规则库中的第i条规则。事实库则由若干为真的条件（即命题）所组成。
对一个新的待验证的命题Q，可使用数据驱动或目标驱动两种推理方式之一，来确认它是
否可由某规则库和事实库推出：
1） 数据驱动的推理是指从事实库开始，每次试图发现规则库中某条能满足所有条件的
规则，并将其结论作为新的事实加入事实库，然后重复此过程，直至发现Q是一个事实或
没有任何新的事实可被发现；
2） 目标驱动的推理是指从目标假设Q出发，每次试图发现规则库中某条含该假设的规
则，然后将该规则的前提作为子目标，确认这些子目标是否和事实库中的事实相匹配，
如果没有全部匹配，则重复此过程，直至发现新的子目标都为真或不能再验证子目标是
否为真。
例如，一个规则库为：
R1 X & B & E -> Y
R2 Y & D -> Z
R3 A->X
事实库为：
A
B
C
D
E
如果想知道命题Z是否为真，数据驱动的推理是从A B C D E开始，依次匹配规则R3（得
到新事实X），R1（得到新事实Y）和R2，得到Z为真的事实；目标驱动的推理是从假设目
标Z开始，依次匹配规则R2（得到新的子目标Y），R1（得到新的子目标X）和R3，得到假
设Z为真的结论。
请编写程序正确、高效的实现这两种推理方式。
输入数据：
程序需要两个命令行参数：
1） <推理方式>：data|goal，分别表示程序应采用数据驱动的推理或目标驱动的推理；
2） <命题>：如Z。
此外，程序还需读入已被命名为rules.txt的规则库和已被命名为facts.txt的事实库。
规则库中的规则可能在千量级，按R1,R2,R3…依次按行排列的，每行一条规则，每条规
则都以Ri C1 & C2 & … & Cn->A的形式表示，Ri和C1之间有1个或多个空格，Ci和&之
间，Cn和->之间，以及->和A之间可以有0或多个空格。事实库中的各事实之间用1个\\n
隔开，每行一个事实。
输出数据：
如果Z能被推理为真，则输出：
TRUE <推理方式：data或goal> <用空格隔开的规则序列：以在所输入的推理方式下，推
出该命题为真的规则被激活的顺序排列>
例如：TRUE goal R2 R1 R3
如果Z不能被推理为真，输出：
UNCERTAIN
评分标准：
在结果正确的前提下，会考虑程序的运行时间。我们会用两组不同的输入数据文件（一
个简单一个复杂）进行测试，简单的输入数据产生的程序输出结果如果正确，获该题满
分的20%即10分（不处理运行时间，除非因程序错误引起的超时运行）；复杂的输入数据
产生的程序输出结果如果正确，获40%即20分，运行时间满分为40%即20分，按各自程序
的运行时间在所有参赛选手的程序的运行时间中所占位置获得相应比例。两种推理方式
各占一半的分数。请仔细阅读并遵守"输入数据"和"输出数据"中的格式要求，如不符合
要求，我们的自动评分程序可能会判定程序不正确。
题目描述：
八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。例如，假设一个3x3矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。
输入数据：
程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。
输出数据：
如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。
自测用例：
如果输入为：start.txt和goal.txt，则产生的输出应为：
5
又例，如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21
评分规则：
1）我们将首先使用和自测用例不同的10个start.txt以及相同的goal.txt，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；
2）每个选手的总分（精确到小数点后6位）=10秒钟内能产生正确结果的测试用例数量x10+（1/产生这些正确结果的测试用例的平均运行毫秒)；
3）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设N=2，然后重复下述过程直至产生最高的9位得分：用随机生成的另外10个有解的start.txt再做测试，并对这10*N个测试用例用2）中公式重新计算总分，N++。