2015慈溪市小学生计算机程序设计竞赛

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 #include

#include #include #include #include

using namespace std; const int maxn = 1010;

const int INF = 0x3f3f3f3f; map frinum;

map > used; int main() {

int n,m; string a,b; int ans = 0;

scanf(\ for(int i = 0;i>a; cin>>b;

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 页

【样例解释】 国王共问了 3 次。

第一次国王说：“我们总共有 3 元奖金”。“编程大侠”说：“最少分配给 1 位大臣，他可以获得所有奖金，即 3 元，因为 3 是一个素数”。

第二次国王说：“我们总共有 4 元奖金”。“编程大侠”说：“最少分配给 2 位大臣，他们每人可以获得 2 元奖金，因为 2 是一个素数”。

第三次国王说：“我们总共有 100 元奖金”。“编程大侠”说：“最少分配给 20 位大臣，他们每人可以获得 5 元奖金，因为 5 是一个素数”。

【数据范围约定】

50%的测试点输入数据保证 1≤T≤5，1≤N≤10000 70%的测试点输入数据保证 1≤T≤10，1≤N≤1000000000 100%的测试点输入数据保证 1≤T≤10，1≤N≤2000000000 #include #include

using namespace std;

bool f(int num)//判断质数? {

if(num==2) return true; if(num%2==0) return false; for(int i=3;i<=sqrt(num);++i) {

if(num%i==0) return false; }

return true; }

int main() {

int n; cin>>n;

int a[n],i,j; for(i=0;i

cin>>a[i]; }

for(i=0;i

for(j=a[i];j>=2;j--) {

if(f(j)&&a[i]%j==0){ cout<

?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 6 页，共 8 页

return 0; }

4. 修建高楼(build.pas)

【问题描述】

C 市有一条东西走向的“市河”。C 市的市长打算在“市河”的其中一条岸边自东往西的 n 个位置（可以将这 n 个位置看成在一条直线上，且位置不会重叠）依次建造高楼。

C 市的设计部门设计了 T 个方案供市长挑选（方案编号为 1 到 T）。每个方案都提供了建造的每幢高楼的高度，自东向西依次为 h1，h2，h3，…，hn-1，hn。每幢楼房的高度在 1 到 n 之间（包括 1 和 n），且各不相同。

市长在挑选设计方案时，喜欢 n 幢高楼中任意 3 幢（包括不连续的 3 幢）有一定的“梯度美”。所谓“梯度美”是指这 3 幢高楼满足：

。

市长喜欢方案中这种“梯度美”现象越多越好。请编程帮市长挑选一下设计方案吧。

【输入数据】输入文件 build.in：输入从文件中读取，输入

共 T+1 行。

第一行两个整数 T 和 n，分别表示设计部门提供的方案总数和打算建造的高楼数。 接下来每一行表示一种方案。第 i+1 行表示第 i 种方案，每行 n 个整数，依次表示每幢高楼打算建造的高度。

【输出数据】输出文件 build.out：结果输出到文件中，输

出共 1 行。

包含两个整数，第一整数为出现“梯度美”次数最多的方案，第二个整数为对应方案“梯度美”出现的次数。如果出现“梯度美”次数最多的方案有多个，输出方案编号较小的方案。

【输入输出样例 1】

build.in 2 5 3 1 2 4 5 3 1 2 5 4 build.out 1 1 【样例 1 解释】 输入中共有 2 个方案，打算建造 5 幢高楼。

第一个方案每幢高楼高度依次为 3，1，2，4，5，其中第 1 幢，第 4 幢和第 5 幢高度出现“梯度美”（3，4，5），这 3 幢高楼的后一幢比前一幢依次高 1。

第二个方案每幢高楼高度依次为 3，1，2，5，4，没有出现“梯度美”。

【输入输出样例 2】

?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 7 页，共 8 页

build.in 2 6 3 5 4 6 1 2 1 6 5 4 2 3 【样例 2 解释】

build.out 2 4 输入中共有 2 个方案，打算建造 6 幢高楼。

第一个方案每幢高楼高度依次为 3，5，4，6，1，2，没有出现“梯度美”。 第二个方案每幢高楼高度依次为 1，6，5，4，2，3，出现了 4 次“梯度美”，分别是（1，

2，3）、(6，5，4)、（6，4，2）、（5，4，3）。

【数据范围约定】

50%的测试点输入数据保证 1≤T≤30，且 3≤n≤500 100%的测试点输入数据保证 1≤T≤50，且 3≤n≤2000

?慈溪市教育局教研室 慈溪市青少年科技辅导员协会 第 8 页，共 8 页

本文来源：https://www.bwwdw.com/article/7o6o.html