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

C/C++程序设计大赛决赛

试 题 目 录

1、排序 .......................................................................... 2 2、行编辑器 ................................................................... 3 3、数字根 ....................................................................... 4 4、投票 .......................................................................... 5 5、线段的交点 ............................................................... 6 6、四塔问题 ................................................................... 8 7、整数划分问题 ........................................................... 9 8、母牛生小牛 ............................................................. 11 9、数列极差问题 ......................................................... 12 10、谁拿了最多奖学金 ............................................... 13

提示：题目后的Sample Input/Output仅是给出符合题目要求的其中一组输入/输出例子，“提交”的程序必须要对所有符合要求的输入数据均能正确计算。判定“提交”是否通过时，会给出另一组不同的测试数据，如程序运行结果不符，将被判为“提交”不通过，要加罚20分钟解题时间。

1、排序

按要求对给定的正整数数列按升序排序〔从小到大〕。

Input：

输入包含多组测试数据，第一行输入测试的组数T，从第二行开始给出T行测试数据。每行第一个数值为该测试数据所包含的正整数个数N，1<=N<=1000，然后输入N个正整数。所有输入的正整数长度均为32bit。

Output：

输出每组测试数据的排序结果。

Sample Input：

2

3 2 1 3

9 1 4 7 2 5 8 3 6 9

Sample Output：

1 2 3

2

1 2 3 4 5 6 7 8 9

2、行编辑器

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。

由于用户在终端上进行输入时，不能保证不出过失，因此，假设在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出过失，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符\"#\"，以表示前一个字符无效；如果发现当前键入的行内过失较多或难以补救，则可以键入一个退行符\"@\"，以表示当前行中的字符均无效。

如果已经在行首继续输入'#'符号无效。

Input：

输入一个多行的字符序列。但行字符总数〔包含退格符和退行符〕不大于250。

Output：

按照上述说明得到的输出。

Sample Input：

whli##ilr#e(s#*s)

3

outcha@putchar(*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作为结束符。输入数值0Output：

对应每行输出该正整数的数字根。

Sample Input：

4

24

39

0

Sample Output：

6

3

4、投票

给出一个奇数N，以及N个正整数〔可重复〕，找出其中重复出现至少(N+1)/2次的正整数。如果不存在，则给出“No solution”的信息。

Input：

输入包含多组数据，每组数据包含两行，第一行输入为奇数N，1<=N<=999999，指示出第二行将要输入的正整数的个数；第二行输入为N个正整数。以数值0为结束符。

Output：

每行对应输出每组输入数据的结果。

5

Sample Input：

5

1 3 2 3 3

11

1 1 1 1 1 5 5 5 5 5 5

7

1 1 1 1 1 1 1

0

Sample Output：

3

5

1

5、线段的交点

在二维直角坐标平面上给定N条线段〔1<=N<=100〕，请输出他们的交点的数目，如果有M

6

〔M>2〕条线段相交于一点，可重复计算。

Input：

输入包含多组测试数据，每组数据的第一行为数值N，1<=N<=100，然后接着输入N行，每行输入四个float型数值，分别代表x1，y1，x2，y2，表示从点〔x1，y1〕到点〔x2，y2〕所构成的一条线段。以数值0为结束符。

Output：

每行对应输出每组测试数据的结果〔交点的数目〕。

Sample Input：

2

0.00 0.00 1.00 1.00

0.00 1.00 1.00 0.00

3

0.00 0.00 1.00 1.00

0.00 1.00 1.00 0.00

0.00 0.00 1.00 0.00

7

0

Sample Output：

1

3

6、四塔问题

“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下，如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？

为了编程方便，您只需要输出这个结果mod 10000的值。

Input：

一个正整数n，表示一共有n个盘子。(0Output：

一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

Sample Input：

8

15

Sample Output：

129

7、整数划分问题

Input：

每组输入是两个整数n和k。(1<=n<=50，1<=k<=n)

Output：

对于每组输入，请输出六行。

第一行： 将n划分成假设干正整数之和的划分数。

第二行： 将n划分成k个正整数之和的划分数。

第三行： 将n划分成最大数不超过k的划分数。

第四行： 将n划分成假设干奇正整数之和的划分数。

第五行： 将n划分成假设干不同整数之和的划分数。

第六行： 打印一个空行。

9

Sample Input：

5 2

Sample Output：

7

2

3

3

3

Hint：

1、将5划分成假设干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

2、将5划分成2个正整数之和的划分为： 3+2, 4+1

3、将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+2

4、将5划分成假设干奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+1

10

5、将5划分成假设干不同整数之和的划分为： 5, 1+4, 2+3

8、母牛生小牛

设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？

Input：

此题有多组数据。每组数据只有一个整数N，独占一行。(1≤N≤50)

Output：

对每组数据，输出一个整数〔独占一行〕表示第N年时母牛的数量

Sample Input：

1

4

5

20

Sample Output：

1

11

2

3

872

9、数列极差问题

在黑板上写了N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个数a和b，然后在数列中加入一个数a×b＋1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M＝max－min。请你编程，对于给定的数列，计算极差。

Input：

输入包含一个测试集。第一个数N表示正整数序列长度〔0＜＝N＜＝1000〕，随后是N个正整数。“0”表示输入结束。

Output：

每个结果一行

Sample Input：

3

12

1

2

3

0

Sample Output：

2

10、谁拿了最多奖学金

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

1) 院士奖学金，每人8000元，期末平均成绩高于80分〔>80〕，并且在本学期内发表1篇或1篇以上论文的学生均可获得；

2) 五四奖学金，每人4000元，期末平均成绩高于85分〔>85〕，并且班级评议成绩高于80分〔>80〕的学生均可获得；

3) 成绩优秀奖，每人2000元，期末平均成绩高于90分〔>90〕的学生均可获得；

4) 西部奖学金，每人1000元，期末平均成绩高于85分〔>85〕的西部省份学生均可获得；

13

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

14

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

15