湖南省第二届“软考杯”大学生程序设计大赛试题
试题 1 人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；
而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”
分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。,苏醒”后的分区不会再转入“睡眠”状态。
有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？
输入,
输入文件的第1行仅包含1个整数M，取值范围是[3,26]，它表示病人大脑的分区数。
第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。
第3行包含3个相邻的英文字母，分别代表刚刚同时“苏醒”的3个分区。
第4行中包含N个用空格分割的字符串，每个字符串包含2个英文字母，分别代表2个相连接的分区。
输出,
如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行,
,WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）
如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行,
,THIS BRAIN NEVER WAKES UP”
示例
输入,
6
11
HAB
AB AC AH BD BC BF CD CF CH DF FH
输出,
WAKE UP IN 3 YEARS
试题 2 测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。
为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。
输入：输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100，元素的值不会大于100000000。
输出：针对输入文件中的每一个数值方阵分别输出如下信息,
1 该数值方阵的序号（按照其在输入文件中的位置从1计起）。格式是：“Area n:” (n代表方阵序号)
2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是,
,M unique vegetation regions,a1 a2,..” (M为区域数目，a1,a2,...等代表每个区域的面积)
3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K为区域数目)
具体的输出格式请参考示例。
示例
输入,
3
2 4 9
17 6 37
29 8 11
4
2 3 12 15
5 7 21 33
4 6 11 17
8 9 13 29
-1
输出,
Area 1,
2 unique vegetation regions,2 3
1 non-unique vegetation regions
Area 2,
2 unique vegetation regions,4 4
2 non-unique vegetation regions
试题 3 某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你，“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求,
1 男演员只能演男角色，女演员只能演女角色。
2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。
3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。
导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。
输入：输入文件的第一行包含用空格分隔的3个正整数，M,F和S。其中M代表剧中的男角色数目，
取值在[1,10]之间；F代表剧中的女角色数目，取值在[1,10]之间；S代表剧中的场景数目，取值在[1,100]
之间。第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。
输出：本剧需要的男女演员的最少数目，具体格式如下,
,You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目
示例
输入,
4 3 6
输出,
You need 3 actors and 2 actresses
Tarzan Jim John Tom
Lucy Cynthia Jane
3 Jim John Tom
2 Tarzan Lucy
2 Jane Cynthia
2 Jim Jane
2 Tarzan Jim
2 Tarzan Jane
试题 4,树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只有左、右两个子树，如图1所示。
图 1
我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值，s代表从根节点到该节点的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。图1中值为13
的节点用(13,RL)表示，值为2的节点用(2,LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值的按层次遍历序列（即先上层后下层、从左至右地遍历）。图1中的二叉树，其节点值的按层次遍历序列为：5,4,8,11,13,4,7,2,1。
输入：输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。
节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括号字符“()”标记，括号之内没有空格。
输出：针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描述的二叉树，则在新的一行中输出字符串“not complete”。
示例
输入,
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
输出,
5 4 8 11 13 4 7 2 1
not complete
试题 5 在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎Baigle的搜索结果不尽人意，比如你按关键词搜索“crazy stone”本意是想搜索一个名为《crazy stone》的电影，结果Baigle
的10万条返回信息大部分是你不需要的。Baigle倾向于把所有包含“crazy”和“stone”两个关键的网页都返回给你，而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了100个
“crazy”，在间隔了5600个词后又出现了100个“stone”，结果这个网页被Baigle放在搜索结果列表的第10位，而它对你来说其实没用。因此，你希望改进现有的搜索引擎，使用户能更明确地控制搜索。
你的设想是：在关键词的前面添加一个距离阈值，限定关键词之间的最大允许距离。比如“0 crazy
stone”表示“crazy”和“stone”两个关键词在文中必须是相邻出现的，“2 crazy stone”表示这两个关键词在文中出现的间隔不能大于2个词。标点和空格不算入间隔，关键词的出现次序也不做限制。我们称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“The director
of Crazy Stone is very young....”和“Why to say the stone is crazy...”两段短文都是合格的。采用这种方法，用户就能更好地控制搜索精度，减少垃圾结果。
你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词的个数大于2，则只需其中任意两个关键词在文中的出现距离不大于距离阈值，就认为该短文是满足搜索要求的。关键词的出现次序不做限定。
输入：输入文件中包含不多于50条搜索元语和不多于250段短文。
1 每条搜索元语占据一行，以“P:”开头，后面依次跟一个非负整数代表距离阈值和若干小写的字符串代表关键词，并有空格分隔。
2 每段短文都以“T:”开头，以“|”结尾。“|”只会出现在短文的末尾。每段短文的长度都不大于255个字符，可能占据多行。每行最多80个字符，短文的每个后续行开头都至少有一个空格。
3 在读取短文时请忽略所有非字母字符，比如原始短文“Don't Rock -- the Boat as Metaphor in
1984”应该被读取为“Dont Rock the Boat as Metaphor in”，“HP2100X”应该被读取为“HPX”。
文件的结尾行包含单独的字符“#”。
输出：输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始（搜索元语的序号是指搜索元语在输入文件中出现的次序，从1开始编号），后面紧跟一个冒号及空格，然后是以升序排列的符合该搜索元语要求的短文序号，短文的序号是指短文在输入文件中出现的次序，从
1开始编号。短文的序号之间以逗号分隔，不含空格。
示例
输入,
P,0 rock art
P,3 concepts conceptions
输出,
1,1,2
2,
P,1 art rock metaphor concepts
T,Rock Art of the Maori|
T,Jazz and Rock - Art Brubeck and Elvis Presley|
T,Don't Rock --- the Boat as Metaphor in 1984,Concepts
and (Mis)-Conceptions of an Art Historian.|
T,Carved in Rock,The Art and Craft of making promises
believable when your `phone bills have gone
through the roof|
#
3,1,2,3,4
试题 6 当我们给大洋彼岸的朋友发出一封email或给家乡的亲人发送一条手机短信时，我们一般不会担心对方收到错误的信息。然而，无论email还是手机短信在抵达目的地前都必需化为电信号穿越无数的电缆和设备，甚至化作无形的电磁波在天空中传播，衰减和噪音时刻都威胁着你发出的信息。为了保证通信的正确性，必需及时发现传输错误并予以纠正，这是现代通信技术中的重要研究内容。一般的解决思路是在原始信息的后面附加一些校验信息，通过这些校验信息来判断传输的正确性。循环冗余码CRC就是这样一种信息校验方法。它的思路是,
待传输的信息是由字节序列组成的，可以看作是一个很长的正二进制数B。当传输B时，在其后附上两个字节的CRC校验值组成B’。CRC校验值不是任意取的，它要使B’能被一个16位的预定义值g整除。信息的接收方也知道g，因此对方只需把接收值除以g看余数是否为零就能判断传输的正确性。在本题中我们设定g = 34943（十进制）。你的任务是编写程序计算任意输入信息对应的CRC校验值。
输入：输入文件中每一行的内容（不包括换行符）就代表一条待传输的信息。每一条待传输信息包含不多于1024个ASCII字符。首字符为“#”的行代表输入的结束。
输出：输出文件的每一行包含两个16进制数（以空格分隔）代表输入文件中对应行中待传输信息的两字节CRC校验值。每个校验值应该在十进制数的0 到34942 之间。
示例
输入,
this is a test
A
#
输出,
77 FD
00 00
0C 86
试题 7 按规矩客户应该在SENY公司把货物发出之后的30天之内付清货款，否则SENY公司就有遭客户赖帐的风险。为了规避风险，SENY公司与一家商业保险公司签订了协议，协议规定：保险公司为SENY的每个客户提供一定额度的支付担保，担保额度与对应客户的财政记录有关。
但在实际运营中，如果某客户的欠款额已经高出保险公司所能提供的担保额度，为了留住客户，
SENY公司还是会继续跟该客户交易并发货。当然，此时超出保险公司担保额度以上的欠款将由SENY
公司独自承担风险。为了保证企业的财政安全，也为了说服保险公司提高对某客户的支付担保额度，
SENY的CEO需要及时了解客户的欠款中有多大比例是不能被保险公司担保的，这个比例就是SENY
内部用来评估客户风险的指标，下面我们将推导这个指标的计算公式。
SENY采用阶跃函数来描述客户c在t时刻的债务，如图2所示,
c
D(t)
图 2
债务风险用债务额与时间的乘积来描述，也就是图2中阶跃函数与水平轴围成区域的面积。时间到之间的债务风险可以写成阶跃函数的积分形式。由于保险公司承担的支付担保额度是一定的，所以超出该额度之上的债务风险要由SENY公司独自承担，该部分风险也可以写成如下积分形式,
0
t
1
t
1
0
t
c
t
D(t)
∫ c
L
1
0
t
c
t
p(D (t) L )?
∫
c 其中
xif x0
p(x)
0if x0
≥
=
<
因此，所有客户的非担保债务风险占总债务风险的比例可以写成如下形式,
1
0
1
0
t
cc
c
t
t
c
c
t
p(D (t) L )
D(t)
∑
∫
∑
∫
你的任务是依据上面的公式编写程序计算上财年的非担保债务风险在总债务风险中的比例。
输入：输入文件的首行中仅包含一个正整数指示文件中的数据样例数目。第二行是空行。然后是数据样例的具体内容。每个数据样例中都包括若干客户在上财年与SENY的交易记录。其中首行都是一个正整数，表示该样例中包含的客户数目。后续若干行中包括该样例中每个客户的交易信息。客户的交易信息包括：首行两个空格分隔的正整数，分别代表该客户的支付担保额度和上财年的交易次数N，
后续N行分别包含其每笔交易的具体内容，包括：交易金额，发货日期和付款日期，三者之间用空格分隔，其中日期以距离该年第一天的偏移天数为记。
输出,输出文件的每一行代表输入文件中对应数据样例中所有客户的非担保债务风险占其总债务风险的比例。该比例值的精度保留到小数点后两位，数值后面紧跟一个英文百分号。
示例
输入,
1
2
40000 3
35000 32 61
15000 45 72
40000 97 123
55000 4
12000 10 52
30000 32 64
33000 44 73
50000 62 94
输出,
11.85%
试题 8 在由方格子拼成的矩形迷宫中，每次只能朝前、后、左、右（分别用N,S,W,E表示）中的任一方向移动一格。每移动一格就消耗一定的能量。某些格子里有障碍物，所以不能移动到这样的格子里；还有些格子里有宝贝，每个宝贝都有其特定的拿起能量和搬运能量。拿起能量是指从格子的地板上拿起宝贝需要花费的能量，搬运能量是指拿着这个宝贝移动一格所消耗的额外能量。
在迷宫里指定一个起点和一个终点，请你谋划一条行进路线，从起点出发沿路收集到所有宝贝并最终抵达终点，要求走这条路线所花费的能量是所有可能路线中最小的。
输入：输入文件的第一行包含两个由空格分开的整数R和C，分别代表迷宫的行数和列数，两者都不大于20。后续的R行，每行C个字符代表了迷宫的地图。其中每个字符表示一个方格子及其属性（’.’
表示空格子，’#’表示有障碍的格子，’*’表示有宝贝的格子，’S’表示起点格子，’T’表示终点格子）。后一行包含一个整数，表示移动一格所花费的能量。再后面一行包含一系列的数据对，每个数据对由用空格分开的两个整数组成，分别表示对应宝贝的拿起和搬运能量。数据对的次序与宝贝在迷宫中的按列从上至下，按行从左至右的先后次序一致。迷宫中最多有10个宝贝，宝贝彼此位于不同的格子中。
输入数据中可能包含多个迷宫样例，每个样例都有上述结构的数据，输入文件的最后一行包含两个由空格分开的0。
输出,针对输入文件中的每个迷宫样例，首先输出“MAP”后跟该样例的序号（从1开始记），在下一行输出走最优路线所花费的能量。如果不存在这样一条路线，请输出“NO WAY”
示例
输入,
5 8
#......T
输出,
MAP1
NO WAY
..#*..#,
..######
...*...#
####S.#*
5
10 50 50 100 30 80
10 10
#........*
..#*..#..,
..######.,
.......#.,
####S..##,
.*.#...#.,
.......#.,
.##.#....#
.*.....#.#
....*..#.T
10
100 400 20 50 150 250 30 70 4 5
0 0
MAP2
17539
试题 1 人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；
而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”
分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。,苏醒”后的分区不会再转入“睡眠”状态。
有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？
输入,
输入文件的第1行仅包含1个整数M，取值范围是[3,26]，它表示病人大脑的分区数。
第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。
第3行包含3个相邻的英文字母，分别代表刚刚同时“苏醒”的3个分区。
第4行中包含N个用空格分割的字符串，每个字符串包含2个英文字母，分别代表2个相连接的分区。
输出,
如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行,
,WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）
如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行,
,THIS BRAIN NEVER WAKES UP”
示例
输入,
6
11
HAB
AB AC AH BD BC BF CD CF CH DF FH
输出,
WAKE UP IN 3 YEARS
试题 2 测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。
为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。
输入：输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100，元素的值不会大于100000000。
输出：针对输入文件中的每一个数值方阵分别输出如下信息,
1 该数值方阵的序号（按照其在输入文件中的位置从1计起）。格式是：“Area n:” (n代表方阵序号)
2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是,
,M unique vegetation regions,a1 a2,..” (M为区域数目，a1,a2,...等代表每个区域的面积)
3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K为区域数目)
具体的输出格式请参考示例。
示例
输入,
3
2 4 9
17 6 37
29 8 11
4
2 3 12 15
5 7 21 33
4 6 11 17
8 9 13 29
-1
输出,
Area 1,
2 unique vegetation regions,2 3
1 non-unique vegetation regions
Area 2,
2 unique vegetation regions,4 4
2 non-unique vegetation regions
试题 3 某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你，“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求,
1 男演员只能演男角色，女演员只能演女角色。
2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。
3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。
导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。
输入：输入文件的第一行包含用空格分隔的3个正整数，M,F和S。其中M代表剧中的男角色数目，
取值在[1,10]之间；F代表剧中的女角色数目，取值在[1,10]之间；S代表剧中的场景数目，取值在[1,100]
之间。第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。
输出：本剧需要的男女演员的最少数目，具体格式如下,
,You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目
示例
输入,
4 3 6
输出,
You need 3 actors and 2 actresses
Tarzan Jim John Tom
Lucy Cynthia Jane
3 Jim John Tom
2 Tarzan Lucy
2 Jane Cynthia
2 Jim Jane
2 Tarzan Jim
2 Tarzan Jane
试题 4,树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只有左、右两个子树，如图1所示。
图 1
我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值，s代表从根节点到该节点的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。图1中值为13
的节点用(13,RL)表示，值为2的节点用(2,LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值的按层次遍历序列（即先上层后下层、从左至右地遍历）。图1中的二叉树，其节点值的按层次遍历序列为：5,4,8,11,13,4,7,2,1。
输入：输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。
节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括号字符“()”标记，括号之内没有空格。
输出：针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描述的二叉树，则在新的一行中输出字符串“not complete”。
示例
输入,
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
输出,
5 4 8 11 13 4 7 2 1
not complete
试题 5 在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎Baigle的搜索结果不尽人意，比如你按关键词搜索“crazy stone”本意是想搜索一个名为《crazy stone》的电影，结果Baigle
的10万条返回信息大部分是你不需要的。Baigle倾向于把所有包含“crazy”和“stone”两个关键的网页都返回给你，而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了100个
“crazy”，在间隔了5600个词后又出现了100个“stone”，结果这个网页被Baigle放在搜索结果列表的第10位，而它对你来说其实没用。因此，你希望改进现有的搜索引擎，使用户能更明确地控制搜索。
你的设想是：在关键词的前面添加一个距离阈值，限定关键词之间的最大允许距离。比如“0 crazy
stone”表示“crazy”和“stone”两个关键词在文中必须是相邻出现的，“2 crazy stone”表示这两个关键词在文中出现的间隔不能大于2个词。标点和空格不算入间隔，关键词的出现次序也不做限制。我们称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“The director
of Crazy Stone is very young....”和“Why to say the stone is crazy...”两段短文都是合格的。采用这种方法，用户就能更好地控制搜索精度，减少垃圾结果。
你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词的个数大于2，则只需其中任意两个关键词在文中的出现距离不大于距离阈值，就认为该短文是满足搜索要求的。关键词的出现次序不做限定。
输入：输入文件中包含不多于50条搜索元语和不多于250段短文。
1 每条搜索元语占据一行，以“P:”开头，后面依次跟一个非负整数代表距离阈值和若干小写的字符串代表关键词，并有空格分隔。
2 每段短文都以“T:”开头，以“|”结尾。“|”只会出现在短文的末尾。每段短文的长度都不大于255个字符，可能占据多行。每行最多80个字符，短文的每个后续行开头都至少有一个空格。
3 在读取短文时请忽略所有非字母字符，比如原始短文“Don't Rock -- the Boat as Metaphor in
1984”应该被读取为“Dont Rock the Boat as Metaphor in”，“HP2100X”应该被读取为“HPX”。
文件的结尾行包含单独的字符“#”。
输出：输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始（搜索元语的序号是指搜索元语在输入文件中出现的次序，从1开始编号），后面紧跟一个冒号及空格，然后是以升序排列的符合该搜索元语要求的短文序号，短文的序号是指短文在输入文件中出现的次序，从
1开始编号。短文的序号之间以逗号分隔，不含空格。
示例
输入,
P,0 rock art
P,3 concepts conceptions
输出,
1,1,2
2,
P,1 art rock metaphor concepts
T,Rock Art of the Maori|
T,Jazz and Rock - Art Brubeck and Elvis Presley|
T,Don't Rock --- the Boat as Metaphor in 1984,Concepts
and (Mis)-Conceptions of an Art Historian.|
T,Carved in Rock,The Art and Craft of making promises
believable when your `phone bills have gone
through the roof|
#
3,1,2,3,4
试题 6 当我们给大洋彼岸的朋友发出一封email或给家乡的亲人发送一条手机短信时，我们一般不会担心对方收到错误的信息。然而，无论email还是手机短信在抵达目的地前都必需化为电信号穿越无数的电缆和设备，甚至化作无形的电磁波在天空中传播，衰减和噪音时刻都威胁着你发出的信息。为了保证通信的正确性，必需及时发现传输错误并予以纠正，这是现代通信技术中的重要研究内容。一般的解决思路是在原始信息的后面附加一些校验信息，通过这些校验信息来判断传输的正确性。循环冗余码CRC就是这样一种信息校验方法。它的思路是,
待传输的信息是由字节序列组成的，可以看作是一个很长的正二进制数B。当传输B时，在其后附上两个字节的CRC校验值组成B’。CRC校验值不是任意取的，它要使B’能被一个16位的预定义值g整除。信息的接收方也知道g，因此对方只需把接收值除以g看余数是否为零就能判断传输的正确性。在本题中我们设定g = 34943（十进制）。你的任务是编写程序计算任意输入信息对应的CRC校验值。
输入：输入文件中每一行的内容（不包括换行符）就代表一条待传输的信息。每一条待传输信息包含不多于1024个ASCII字符。首字符为“#”的行代表输入的结束。
输出：输出文件的每一行包含两个16进制数（以空格分隔）代表输入文件中对应行中待传输信息的两字节CRC校验值。每个校验值应该在十进制数的0 到34942 之间。
示例
输入,
this is a test
A
#
输出,
77 FD
00 00
0C 86
试题 7 按规矩客户应该在SENY公司把货物发出之后的30天之内付清货款，否则SENY公司就有遭客户赖帐的风险。为了规避风险，SENY公司与一家商业保险公司签订了协议，协议规定：保险公司为SENY的每个客户提供一定额度的支付担保，担保额度与对应客户的财政记录有关。
但在实际运营中，如果某客户的欠款额已经高出保险公司所能提供的担保额度，为了留住客户，
SENY公司还是会继续跟该客户交易并发货。当然，此时超出保险公司担保额度以上的欠款将由SENY
公司独自承担风险。为了保证企业的财政安全，也为了说服保险公司提高对某客户的支付担保额度，
SENY的CEO需要及时了解客户的欠款中有多大比例是不能被保险公司担保的，这个比例就是SENY
内部用来评估客户风险的指标，下面我们将推导这个指标的计算公式。
SENY采用阶跃函数来描述客户c在t时刻的债务，如图2所示,
c
D(t)
图 2
债务风险用债务额与时间的乘积来描述，也就是图2中阶跃函数与水平轴围成区域的面积。时间到之间的债务风险可以写成阶跃函数的积分形式。由于保险公司承担的支付担保额度是一定的，所以超出该额度之上的债务风险要由SENY公司独自承担，该部分风险也可以写成如下积分形式,
0
t
1
t
1
0
t
c
t
D(t)
∫ c
L
1
0
t
c
t
p(D (t) L )?
∫
c 其中
xif x0
p(x)
0if x0
≥
=
<
因此，所有客户的非担保债务风险占总债务风险的比例可以写成如下形式,
1
0
1
0
t
cc
c
t
t
c
c
t
p(D (t) L )
D(t)
∑
∫
∑
∫
你的任务是依据上面的公式编写程序计算上财年的非担保债务风险在总债务风险中的比例。
输入：输入文件的首行中仅包含一个正整数指示文件中的数据样例数目。第二行是空行。然后是数据样例的具体内容。每个数据样例中都包括若干客户在上财年与SENY的交易记录。其中首行都是一个正整数，表示该样例中包含的客户数目。后续若干行中包括该样例中每个客户的交易信息。客户的交易信息包括：首行两个空格分隔的正整数，分别代表该客户的支付担保额度和上财年的交易次数N，
后续N行分别包含其每笔交易的具体内容，包括：交易金额，发货日期和付款日期，三者之间用空格分隔，其中日期以距离该年第一天的偏移天数为记。
输出,输出文件的每一行代表输入文件中对应数据样例中所有客户的非担保债务风险占其总债务风险的比例。该比例值的精度保留到小数点后两位，数值后面紧跟一个英文百分号。
示例
输入,
1
2
40000 3
35000 32 61
15000 45 72
40000 97 123
55000 4
12000 10 52
30000 32 64
33000 44 73
50000 62 94
输出,
11.85%
试题 8 在由方格子拼成的矩形迷宫中，每次只能朝前、后、左、右（分别用N,S,W,E表示）中的任一方向移动一格。每移动一格就消耗一定的能量。某些格子里有障碍物，所以不能移动到这样的格子里；还有些格子里有宝贝，每个宝贝都有其特定的拿起能量和搬运能量。拿起能量是指从格子的地板上拿起宝贝需要花费的能量，搬运能量是指拿着这个宝贝移动一格所消耗的额外能量。
在迷宫里指定一个起点和一个终点，请你谋划一条行进路线，从起点出发沿路收集到所有宝贝并最终抵达终点，要求走这条路线所花费的能量是所有可能路线中最小的。
输入：输入文件的第一行包含两个由空格分开的整数R和C，分别代表迷宫的行数和列数，两者都不大于20。后续的R行，每行C个字符代表了迷宫的地图。其中每个字符表示一个方格子及其属性（’.’
表示空格子，’#’表示有障碍的格子，’*’表示有宝贝的格子，’S’表示起点格子，’T’表示终点格子）。后一行包含一个整数，表示移动一格所花费的能量。再后面一行包含一系列的数据对，每个数据对由用空格分开的两个整数组成，分别表示对应宝贝的拿起和搬运能量。数据对的次序与宝贝在迷宫中的按列从上至下，按行从左至右的先后次序一致。迷宫中最多有10个宝贝，宝贝彼此位于不同的格子中。
输入数据中可能包含多个迷宫样例，每个样例都有上述结构的数据，输入文件的最后一行包含两个由空格分开的0。
输出,针对输入文件中的每个迷宫样例，首先输出“MAP”后跟该样例的序号（从1开始记），在下一行输出走最优路线所花费的能量。如果不存在这样一条路线，请输出“NO WAY”
示例
输入,
5 8
#......T
输出,
MAP1
NO WAY
..#*..#,
..######
...*...#
####S.#*
5
10 50 50 100 30 80
10 10
#........*
..#*..#..,
..######.,
.......#.,
####S..##,
.*.#...#.,
.......#.,
.##.#....#
.*.....#.#
....*..#.T
10
100 400 20 50 150 250 30 70 4 5
0 0
MAP2
17539
