〔ACM算法与程序设计〕期末问题集.docVIP

一、1、两倍/problem?id=2807 Description给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。 Input输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。 Output对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。 Sample Input 1 4 3 2 9 7 18 22 0 2 4 8 10 0 7 5 11 13 1 3 0 -1 Sample Output 3 2 0 /problem?id=2715 Description某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 1) 院士奖学金，每人8000元，期末平均成绩高于80分（80），并且在本学期内发表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输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。 Sample Input 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 Sample Output ChenRuiyi 9000 28700 二、字符串处理 1、古代密码 - /problem?id=2820 Description古罗马帝王有一个包括各种部门的强大政府组织。其中有一个部门就是必威体育官网网址服务部门。为了保险起见，在省与省之间传递的重要文件中的大写字母是加密的。当时最流行的加密方法是替换和重新排列。 替换方法是将所有出现的字符替换成其它的字符。有些字符会碰巧替换成它自己。例如：替换规则可以是将A 到 Y替换成它的下一个字符，将Z替换成 A，如果原词是 VICTORIOUS 则它变成 WJDUPSJPVT。 排列方法改变原来单词中字母的顺序。例如：将顺序 2, 1, 5, 4, 3, 7, 6, 10, 9, 8 应用到 VICTORIOUS 上，则得到IVOTCIRSUO。 人们很快意识到单独应用替换方法或排列方法，加密是很不保险的。但是如果结合这两种方法，在当时就可以得到非常可靠的加密方法。所以，很多重要信息先使用替换方法加密，再将加密的结果用排列的方法加密。用两中方法结合就可以将VICTORIOUS 加密成JWPUDJSTVP。 考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义，所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码，现在他们想检查解读的是否正确。他们需要一个计算机程序来验证她，你的任务就是写这个验证程序。 Input输入有两行。第一行是石台上的文字。文字中没有空