C++程序设计大赛决赛(广工).doc

广东工业大学第一届C/C+程序设计大赛决赛试 题 目 录1、排序22、行编辑器23、数字根34、投票35、线段的交点46、四塔问题57、整数划分问题58、母牛生小牛69、数列极差问题710、谁拿了最多奖学金7提示：题目后的Sample Input/Output仅是给出符合题目要求的其中一组输入/输出例子，“提交”的程序必须要对所有符合要求的输入数据均能正确计算。判定“提交”是否通过时，会给出另一组不同的测试数据，如程序运行结果不符，将被判为“提交”不通过，要加罚20分钟解题时间。1、排序按要求对给定的正整数数列按升序排序（从小到大）。Input：输入包含多组测试数据，第一行输入测试的组数T，从第二行开始给出T行测试数据。每行第一个数值为该测试数据所包含的正整数个数N，1=N=1000，然后输入N个正整数。所有输入的正整数长度均为32bit。Output：输出每组测试数据的排序结果。Sample Input：23 2 1 39 1 4 7 2 5 8 3 6 9Sample Output：1 2 31 2 3 4 5 6 7 8 92、行编辑器一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。 由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符#，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符，以表示当前行中的字符均无效。如果已经在行首继续输入#符号无效。Input：输入一个多行的字符序列。但行字符总数（包含退格符和退行符）不大于250。 Output：按照上述说明得到的输出。 Sample Input：whli#ilr#e(s#*s)outchaputchar(*s=#+);Sample Output：while(*s)putchar(*s+);3、数字根定义：将一个正整数各个数位上的数字求和，如果各个数位上的数字和为一位数，即为这个正整数的“数字根”，否则重复以上过程，直至各个数位的数字之和为一个一位数。例子：正整数24，由于2+4=6，因此24的数字根为6。又如正整数39，由于3+9=12，1+2=3，因此39的数字根为3。Input：输入多行的数值，以数值0作为结束符。输入数值0n=100000。Output：对应每行输出该正整数的数字根。Sample Input：24390Sample Output：634、投票给出一个奇数N，以及N个正整数（可重复），找出其中重复出现至少(N+1)/2次的正整数。如果不存在，则给出“No solution”的信息。Input：输入包含多组数据，每组数据包含两行，第一行输入为奇数N，1=N=999999，指示出第二行将要输入的正整数的个数；第二行输入为N个正整数。以数值0为结束符。Output：每行对应输出每组输入数据的结果。Sample Input：51 3 2 3 3111 1 1 1 1 5 5 5 5 5 571 1 1 1 1 1 10Sample Output：3515、线段的交点在二维直角坐标平面上给定N条线段（1=N2）条线段相交于一点，可重复计算。Input：输入包含多组测试数据，每组数据的第一行为数值N，1=N=100，然后接着输入N行，每行输入四个float型数值，分别代表x1，y1，x2，y2，表示从点（x1，y1）到点（x2，y2）所构成的一条线段。以数值0为结束符。Output：每行对应输出每组测试数据的结果（交点的数目）。Sample Input：20.00 0.00 1.00 1.000.00 1.00 1.00 0.0030.00 0.00 1.00 1.000.00 1.00 1.00 0.000.00 0.00 1.00 0.000Sample Output：136、四塔问题“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下，如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？为了编程方便，您只需要输出这个结果mod 10000的值。 Input：一个正整数n，表示一共有n个盘子。(0n=50000) Output：一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。 Sample Input：15Sample Output：1297、整数划分问题Input：每组输入是两个整数n和k。(1=n=50，1=k80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（85），并且班级评议成绩高于80分（80）的学生均可获得； 3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（90）的学生均可获得； 4) 西部奖学金，每人1000元，期末平均成绩高于85分（85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（80）的学生干部均可获得。只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如某学生的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。 现在给出若干学生的相关数据，请计算哪位同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。 Input：输入的第一行是一个整数N（1=N=100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。Output：输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓