ACM编程比赛入门题目集(7)

奖学金

Time limit: 1s Memory limit: 32768K

Total Submit : 363 Accepted Submit : 218

【问题描述】

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是： 7 279 5 279

这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是： 5 279

7 279

则按输出错误处理，不能得分。

【要求】

【数据输入】输入包含多组测试数据，每个测试数据有n+1行。

第1行为一个正整数n，表示该校参加评选的学生人数。

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。 所给的数据都是正确的，不必检验。

【数据输出】对于每个测试数据输出5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。两个相邻测试数据间用一个空行隔开。

【样例输入】 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 8

80 89 89

88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98

【样例输出】 6 265 4 264 3 258 2 244 1 237

8 265 2 264 6 264 1 258 5 258

纪念品分组

Time limit: 1s Memory limit: 32768K Total Submit : 92 Accepted Submit : 51

【问题描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【要求】

【数据输入】 输入包含多组测试数据，每个测试数据包含n+2行： 第1行包括一个整数w，为每组纪念品价格之和的上限。 第2行为一个整数n，表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。 1 <= n <= 30000, 80 <= w <= 200

【数据输出】对每个测试数据，输出一行，包含一个整数，即最少的分组数目。 相邻两个测试数据间用一个空行隔开。

【样例输入】 100 9 90 20 20 30 50 60 70 80 90

【样例输出】 6

统计数字

Time limit: 1s Memory limit: 32768K Total Submit : 165 Accepted Submit : 58

【问题描述】

某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【要求】

【数据输入】包含多个测试数据，每个包含n+1行： 第1行是整数n，表示自然数的个数。 第2~n+1行每行一个自然数。

1<=n<=200000，每个数均不超过1 500 000 000（1.5*109）

【数据输出】对每个测试数据输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

相邻两个测试数据间用一个空行隔开。

【样例输入】 8 2 4 2 4 5 100 2

100

【样例输出】 2 3 4 2 5 1 100 2

矩阵取数游戏

Time limit: 1s Memory limit: 32768K Total Submit : 150 Accepted Submit : 27

【问题描述】

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾；

3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；

4. 游戏结束总得分为m次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

【要求】

【数据输入】输入有多个测试数据，每个包括n+1行： 第1行为两个用空格隔开的整数n和m。

第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。 1<=n, m<=80, 0<=aij<=1000

【数据输出】对每个数据，输出一行，为一个整数，即输入矩阵取数后的最大得分。相邻两个输出间用一个空行隔开。

【样例输入】 1 4 4 5 0 5

2 10

96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67

【样例输出】 122 316994