星空间站的名称或起点、终点星球的名称，正整数capacityi是飞船从sourcei到destinationi一次能运载的最大旅客流量。每个名称是由A～Z之间三个大写字母组成的字符串，例如：ZJU。
测试数据中不包含任何到达起点星球的信息以及任何从终点星球出发的信息。 输出要求： 对每一组测试，在一行里输出终点星球接待站应具有的最小容量，使得每艘飞船在到达时都可以保证让全部旅客下船。
38.猴子选大王
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 输入数据：输入m,n m,n 为整数，n 输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 39.纸牌游戏 任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后?从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 40.拓扑排序 [问题描述] 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，再编写函数实现图的拓扑排序。 [基本要求] 选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。 [测试数据] 利用下图中的数据调试程序 C4C2C1C12C9C10C11 41.走迷宫 C5C3C7C8C6 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 要求： 1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过； 3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 找出走出迷宫的所有路径，以及最短路径。 42.敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 43.HTML文档标记匹配算法 要求：输入一段HTML代码，判断该代码是否符合HTML的语法 提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为 ? :HTML文档 ?
:节的头部
?
:段落 ? 。。。
HTML语言有合理的嵌套，如
44.分配策略
有n个人去分m个蛋糕，每个蛋糕的底面积不等。（假设蛋糕的高度是相同的）
要求，1：一个人只能从某块蛋糕中分到其中的一块，不能从2个以上的不同蛋糕中分得蛋糕。
2：要求每个人分到的蛋糕块体积相同，同时，每个分到的蛋糕的体积是最大的。
对于给定的n，m以及m各蛋糕的底面积，求分配的方案，以及每人能分到多大面积的蛋糕。 例如：假定有6个人分3块蛋糕，每块底面积的大小分别为：3，9，7。
那么最终的分配方案为：1人分半径为3蛋糕，2人分半径为7的蛋糕，3人分半径为9的蛋糕，每人能分到面积为3的蛋糕。
45.语言中平衡符号的问题
要求：设C语言程序代码中包含如下符号/* */，（），[]，{}，编写程序检测一段C代码中上述符号是否正确。
46.烫手山芋问题
一群小孩编号为1，2，?，n(n>0)围成一圈，有一个刚出锅的山芋在他们之间传递。假设刚开始由1号拿着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿
着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？
47.入学考试问题
某地大学入学考试，相关信息如下： (1)参加人数：10万。
(2)共有8门考试课程，每门课程满分均为100分，所有课程成绩均进行了4舍5入的处理，考生的总分也照此处理。
(3)所有考生的考试成绩保存在文件scores.txt中，文件格式如下：
每个考生成绩一行，每行格式如下：最开始为考生姓名，然后为每门课程的分数，考生姓名与课程分数之间，以及不同课程分数之间均用一个英文逗号隔开，如： 张三,98,92,60,54,87,75,86,92 个别考生成绩行的格式可能会有误。
(4)共招收三个批次的学生，第一批次30000人，第二批次60000人，第三批次10000人。录取顺序为：第一批次，第二批次，第三批次。 程序要求：
(1)确定每一批次的录取分数线，并将批次、分数线、实际录取人数输出到文本文件soutput.txt中，每一批次录取信息占一行，格式自定。确定分数线时，如果在分数线处有多名考生，则将这些考生全部录取，即每一批次的实际录取人数可能会超过预定人数。例如：假定在确定第一批次分数线时，有7800人的总分高于等于750分，有8050人的总分高于等于749分，则第一批次分数线应确定为749分，实际录取人数为8050人。
(2)如果考生成绩行的格式不对，则丢弃该考生的成绩，不作为确定分数线的依据，但要求将该考生姓名输出到文本文件serror.txt中，格式自定。
(3)将总分为650分的考生姓名输出到文本文件soutput.txt中，格式自定。
(4)将第三批次录取的所有考生的平均成绩（4舍5入）输出到文本文件soutput.txt中，格式自定。
(5)要求将下面两个时间值（单位为秒）输出到文件soutput.txt的最后：从打开scores.txt文件到读完所有考生成绩的时间；从打开scores.txt文件到程序结束的时间。
48.括号嵌套问题
某个序列完全由圆括号组成，一个“（”和一个“）”称为一对括号，且序列中的括号成对出现。设n为序列中出现的括号对数，k为序列中括号的最大嵌套深度；那么，序列“((()()()))()(())”的n为8，k为3。
1、请编程判断任意给定的圆括号序列，是否是一个深度为k的序列。 要求：（1）先输入嵌套深度k，然后输入任意一个序列，最后给出判定结果（是，不是，或者输入序列中的括号不配对）
（2）可以反复输入数据，当k为0时，程序结束。while(k!=0)
输入示例： 3
((()()()))()(()) 2
((()()()))()(()) 5
(()()()))()((((()))))
输出的判定结果： 测试1：YES 测试2：NO
测试3：括号不配对
2、编程输出括号对数为n，嵌套深度为k的所有序列。(1<=k<=n<=10) 比如，当n=3，k=2时，共有3个嵌套深度为2的序列，即“()(())”、“(()())”、“(())()”。 要求：（1）每一个输出序列单独占一行；并在末尾输出“×对括号，×层嵌套问题,共求出×××种序列”。
（2）可以反复输入数据，当k>n时，程序结束。
输出结果示例（n=5，k=3）： 1: ((()()())) 2: ((()())()) 3: ((()()))() 4: ((())(())) 5: ((())()()) 6: ((())())() 7: ((()))(()) 8: ((()))()() 9: (()(()())) 10: (()(())()) 11: (()(()))() 12: (()()(())) 13: (())((())) 14: ()((()())) 15: ()((())()) 16: ()((()))() 17: ()(()(())) 18: ()()((()))
5对括号，3层嵌套问题,共求出18种情况
3、求解括号对数为n，嵌套深度为k的序列的总数（不输出具体序列）。(1<=k<=n<=30) 输入示例： 3 2 15 3 20 11 输出结果： 3 2：3种
15 3：497845种 2011：94817125种
49.树重建
给出一棵标号树的BFS序列和DFS序列，设计一个算法重新建立这棵树（结点数n≤1000）。当某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。例如一棵树的BFS序列为43512876，DFS序列为43172658，则一棵满足条件的树如右图所示。 输入格式
第一行输入结点数n。第二行n个用空格隔开的整数，描述这棵树的BFS序列；第三行n个用空格隔开的整数，描述这棵树的DFS序列。 输出格式
一共输出n-1行，每行两个整数i,j描述一条边，表示第i个结点与第j个结点之间连一条边。 样例输入 8
4 3 5 1 2 8 7 6 4 3 1 7 2 6 5 8 样例输出 4 5 5 8 4 3 3 2 2 6 3 1 1 7
提示：我们曾经遇到过相似的题目，给出一棵二叉树的先序，中序，后续遍历中的其中两种，要你还原这棵二叉树。而这题改为了给出DFS和BFS序列，虽然形式上变了，但是原理还是相似的，我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决。 拿题目数据做例子。首先，无论是BFS（广度优先搜索）序列还是DFS（深度优先搜索）序列，第一个点都必定是根结点。接着我们看BFS序列，跟在根结点4后面的连续若干个结点就是4的儿子结点，但是究竟有多少个是4的儿子呢？首先，题目中的一个条件说：“某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问”，因此4的儿子应该是按由小到大出现在BFS序列中的。后面3<5，但是5>1，所以1就肯定不是4的儿子。然而即使后面若干个数满足升序的条件，也不一定全都是4的儿子，这时我们就要借助DFS序列了。因为DFS的规律是遍历完一棵子树才到另一棵，所以4的儿子在DFS序列中也是按由小到大出现，只是它们之间可能被若干个结点隔开罢了。根据这两个条件，我们就能判断哪些是4的儿子了。例如在BFS序列中紧挨着4出现的3,5，在DFS序列中也是按照由小到大的顺序先出现3，再出现5，因此3,5都是4的儿子。
接下来怎么做呢？由于4的儿子都确定了，剩下的就是把4的每一棵子树都确定下来，而这就是一个子问题了。若我们确定了根结点有k个儿子，若第i个儿子在DFS中的位置为P1，第i+1个儿子在DFS中的位置为P2，则在DFS序列中位置P1与P2之间的所有结点就是以第i个儿子为根的子树的结点。而我们可以建立一个队列，每确定一个结点就把它加到队列里面去，模拟BFS的过程。在模拟广搜的过程中，若当前要处理的结点为k，由于以k为根的整棵子树在DFS序列中是连续的一段，而究竟是那一段在前面的广搜过程中是可以顺带求出的。然后我们利用BFS序列和DFS序列中连续的一段确定出k的所有儿子，并加到广搜队列里面。直到广搜结束，问题就解决了。