2015 年慈溪市小学生计算机程序设计比赛复赛
试题
比赛时间：2015 年 12 月 20 日上午 8:30—10:30
题目概览 中文题目名称 提交源程序文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 运行内存上限 朋友 friend.pas friend.in friend.out 1秒 20 5 50MB 排队 lineup.pas lineup.in lineup.out 1秒 20 5 50MB 爱好数学的国王 king.pas king.in king.out 1秒 20 5 50MB 修建高楼 build.pas build.in build.out 1秒 20 5 50MB 注意事项 1．选手比赛时，都应在 E 盘的根目录下建立自己的比赛文件夹，该文件夹的名称为考生的考号。同时需在比赛文件夹内为每题建立对应的题目目录（名称与题目名称相同，严格区分大小写）。例如：假设题目有 cashier、dune、manhattan 三题。参赛号为 cx08 的选手，其最终提交的文件为 cashier. pas、dune.pas、manhattan.
pas，则该选手应提交的目录结构如下所示： E|---cx08 2.
|---cashier/
| |---cashier. pas |--- dune/ | |--- dune.pas |---manhattan/ |---manhattan. pas
选手根据题目要求，将自己提交的源文件，放在该题的题目目录下（只需递交源文件，评测时以源
文件为准，不测可执行程序，收卷时只复制 E 盘比赛文件夹，凡放错位置的文件或以书面形式提交的答卷一律视作无效）； 3.
比赛中涉及的所有文件名（包括源程序名、输入文件名、输出文件名、答案文件名），都必须严格按
照题目要求命名，严格区分大小写。例如：题目要求输入文件名为 game.in，则程序中必须按照该名字打开文件，不能使用 Game.in、GAME.IN 等名字； 4.
程序中必须采用文件读写的方法来实现数据的输入和结果的输出，即程序运行时所需输入数据应从
题中指定的输入文件中读取（而不得采用键盘输入的方式），程序运行的结果应写入到题中指定的文件中（而不是输出到屏幕上）； 5.
用于提供输入数据和记录输出结果的文件的名称都已在题中具体规定，选手程序在调用它们时不得为其指定任何特别的路径； 6.
输出文件的格式应该严格符合题目的要求，例如：不得有多余的空格等字符；一行结束，应跟有回车换行符；
?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 1 页，共 8 页
7.如遇机器故障，一律请监考老师处理，比赛中途及结束时都不得自行关机或重启机器，否则后果自负。
1．朋友(friend.pas)
【问题描述】
同学们应该学会多交一些好朋友。朋友关系是相互的，A 是 B 的好朋友，则 B 也是 A 的好朋友。朋友关系是不传递的，A 是 B 的好朋友，B 是 C 的好朋友，但 A 和 C 不一定是好朋友。现在给出某小学部分同学之间的朋友关系，请编程统计朋友最多的人有多少个好朋友。
【输入数据】输入文件 friend.in：输入从文件中读取，输入共
m+1 行。
第 1 行是两个整数 n 和 m，分别表示同学总人数和朋友关系对数。
第 2 行到第 m+1 行，描述了 m 对朋友关系。每行两个用单个空格隔开的同学姓名。 每个人的姓名仅由小写字母组成，且 1≤姓名的长度≤10。
【输出数据】输出文件 friend.out：结果输出到文件中，输
出共 1 行。
一个整数，表示朋友最多的人有多少个好朋友。
【输入输出样例 1】
friend.in 4 3 lucy lily jam lily jam peter 【样例 1 解释】
4 个人，3 对朋友关系。 lucy 只有一个朋友 lily； jam 有两个朋友 lily 和 peter； lily 有两个朋友 lucy 和 jam； peter 只有一个朋友 jam。
friend.out 2 所以 lily 和 jam 朋友最多，都是 2 个。
【输入输出样例 2】
friend.in 6 5 andy bob bella andy bob andy andy cassie cassie bob friend.out 3 ?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 2 页，共 8 页
【样例 2 解释】
6 个人，5 对朋友关系。其中第 1 对朋友关系“andy bob”和第 3 对朋友关系“bob andy” 重复。
andy 有三个朋友，分别是 bob、bella 和 cassie； bob 有两个朋友 andy 和 cassie； bella 只有一个朋友 andy；
cassie 有两个朋友 bob 和 andy；
另外 2 个人没有朋友（这两个人在输入中没有出现）。 所以 andy 的朋友最多，有 3 个朋友。
【数据范围约定】
50%以上的测试点输入数据保证朋友关系没有重复。
100%的测试点输入数据保证#include
#include
using namespace std; const int maxn = 1010;
const int INF = 0x3f3f3f3f; map
map
int n,m; string a,b; int ans = 0;
scanf(\ for(int i = 0;i
if(used[a][b]==0){
frinum[a] = frinum[a]+1;
frinum[b] = frinum[b]+1;
used[a][b] = used[b][a] = 1;
ans = max(frinum[a],max(ans,frinum[b])); }
?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 3 页，共 8 页
。
}
printf(\
return 0; }
2．排队(lineup.pas)
【问题描述】
在很多场合，我们都需要排队，比如超市付款，医院看病，就餐等等。“尊老爱幼”是中华名族的传统美德，所以在排队的过程中，遇到老人、幼儿我们应该主动让他们排在前面。请按以下 4 条规则编写一个排队的程序。
(1) 老人（年龄 ≥ 60 岁）和幼儿（年龄 ≤ 6 岁）比其他人（6 岁 < 年龄 < 60 岁）优先
排在队伍的前面，且所有幼儿排在所有老人的前面。 (2) 老人按年龄从大到小的顺序排队，年龄大的优先，年龄相同时，先到的人排在前面。 (3) 幼儿按年龄从小到大的顺序排队，年龄小的优先，年龄相同时，先到的人排在前面。 (4) 其他人只按到达的先后顺序排队。
【输入数据】输入文件 lineup.in：输入从文件中读取，输入
共 n+1 行。
第 1 行一个整数 n，表示排队的总人数。
第 2 行到第 n+1 行，按照到达的先后顺序给出了每个人的基本信息。每行两个整数，第一个整数表示这个人的编号（编号保证不会重复，但不保证连续），第二个整数表示这个人的年龄。
【输出数据】输出文件 lineup.out：结果输出到文件中，输
出共 n 行。
每行一个人的编号，表示从前往后的排队结果。
【输入输出样例】
lineup.in 8 1 14 3 6 4 5 5 62 11 48 17 25 21 60 13 62 【样例解释】 lineup.out 4 3 5 13 21 1 11 17 共有 8 个人参加排队。编号为 3 和 4 的两个人为幼儿，年龄分别为 6 岁和 5 岁。编号为 5 、21 和 13 的三个人为老人，年龄分别为 62 岁、60 岁和 62 岁。根据排队规则，
?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 4 页，共 8 页
老人和幼儿排在其他人的前面，而幼儿又排在老人的前面，所以先排编号 3 和 4 的幼儿。幼儿按年龄从小到大的顺序排队，所以第一个人是 4 号，然后是 3 号。接下来排老人，老人年龄大的先排，所以先排 5 号和 13 号，但 5 号比 13 号先到，所以先排 5 号，然后 13 号，接下来 21
号。剩下的人不论年龄大小，全部按到达的顺序排队，依次为 1 号、11 号和 17 号。
【数据范围约定】
40%的测试点输入数据保证 1≤n≤99，且每个人的年龄都不相同。 60%的测试点输入数据保证 1≤n≤1000。
100%的测试点输入数据保证 1≤n≤30000， 1≤人的编号≤32000，2≤人的年龄≤100。
3．爱好数学的国王(king.pas)
【问题描述】
Z 国的国王是一个非常爱好数学的国王。一天他对着他的那些大臣说：“素数真是一种神奇的正整数，除了1和它本身外，不能被其他任何正整数整除，2是最小的素数，有无穷多个啊……它还有一个美妙的名字：质数，……数学多么有趣啊……”。
Z 国今年风调雨顺，百姓丰衣足食。为了奖励他那帮管理有方的大臣，他决定把全部的 N 元奖金平均分配给其中的 K 位大臣，但酷爱数学的国王要求这 K 位大臣每人拿到的奖金必须是个素数。哪个大臣能够解决这个数学问题，国王就把奖金给这个大臣和另外的 K-1 人。
大臣们都想自己获得更多的奖金，所以希望分得奖金的大臣人数 K 越少越好。机智的大臣请来了“编程大侠”来帮忙解决这个问题。国王的间谍得知了这个情况后向国王汇报了大臣的行为。国王早就听说“编程大侠”的厉害，于是决定问 T 次这个问题，来试探一下 “编程大侠”的真正实力。
【输入数据】输入文件 king.in：输入从文件中读取，输入
共 T+1 行。
第 1 行一个整数 T，表示国王问了 T 次。
接下来 T 行每行一个整数 N，表示国王打算分配给大臣的总奖金。
【输出数据】输出文件 king.out：结果输出到文件中，输
出共 T 行。
第 i 行一个整数 K，表示最少多少位大臣来平分输入中对应的全部奖金。如果找不到满足国王要求的分配办法，请输出“0”（输出时不包含双引号）。
【输入输出样例】
king.in 3 3 4 100 king.out 1 2 20 ?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 5 页，共 8 页