2015年慈溪市小学生计算机程序设计比赛
复赛试题
比赛时间：2015年12月20日上午8:30—10:30
题目概览
注意事项
1．选手比赛时，都应在E盘的根目录下建立自己的比赛文件夹，该文件夹的名称为考生的考号。同时需在比赛文件夹内为每题建立对应的题目目录（名称与题目名称相同，严格区分大小写）。例如：假设题
目有cashier、dune、manhattan三题。参赛号为cx08的选手，其最终提交的文件为cashier. pas、dune.pas、manhattan. pas，则该选手应提交的目录结构如下所示：
E|---cx08
|---cashier/
| |---cashier. pas
|--- dune/
| |--- dune.pas
|---manhattan/
|---manhattan. pas
2. 选手根据题目要求，将自己提交的源文件，放在该题的题目目录下（只需递交源文件，评测时以源文件为准，不测可执行程序，收卷时只复制E盘比赛文件夹，凡放错位置的文件或以书面形式提交的答卷一律视作无效）；
3. 比赛中涉及的所有文件名（包括源程序名、输入文件名、输出文件名、答案文件名），都必须严格按照题目要求命名，严格区分大小写。例如：题目要求输入文件名为game.in，则程序中必须按照该名字打开文件，不能使用Game.in、GAME.IN等名字；
4. 程序中必须采用文件读写的方法来实现数据的输入和结果的输出，即程序运行时所需输入数据应从题中指定的输入文件中读取（而不得采用键盘输入的方式），程序运行的结果应写入到题中指定的文件中（而不是输出到屏幕上）；
5. 用于提供输入数据和记录输出结果的文件的名称都已在题中具体规定，选手程序在调用它们时不得为其指定任何特别的路径；
6. 输出文件的格式应该严格符合题目的要求，例如：不得有多余的空格等字符；一行结束，应跟有回车换行符；
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解释】
4个人，3对朋友关系。
lucy只有一个朋友lily；
jam有两个朋友lily和peter；
lily有两个朋友lucy和jam；
peter只有一个朋友jam。
所以lily和jam朋友最多，都是2个。
【样例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%的测试点输入数据保证2≤n≤100，1≤m≤1000，且没有自己跟自己的朋友关系。
2．排队(lineup.pas)
【问题描述】
在很多场合，我们都需要排队，比如超市付款，医院看病，就餐等等。“尊老爱幼”是中华名族的传统美德，所以在排队的过程中，遇到老人、幼儿我们应该主动让他们排在前面。请按以下4条规则编写一个排队的程序。
(1)老人（年龄≥60岁）和幼儿（年龄≤6岁）比其他人（6岁< 年龄< 60岁）
优先排在队伍的前面，且所有幼儿排在所有老人的前面。
(2)老人按年龄从大到小的顺序排队，年龄大的优先，年龄相同时，先到的人排在前面。
(3)幼儿按年龄从小到大的顺序排队，年龄小的优先，年龄相同时，先到的人排在前面。
(4)其他人只按到达的先后顺序排队。
【输入数据】
输入文件lineup.in：输入从文件中读取，输入共n+1行。
第1行一个整数n，表示排队的总人数。
第2行到第n+1行，按照到达的先后顺序给出了每个人的基本信息。每行两个整数，第一个整数表示这个人的编号（编号保证不会重复，但不保证连续），第二个整数表示这个人的年龄。
【输出数据】
输出文件lineup.out：结果输出到文件中，输出共n行。
每行一个人的编号，表示从前往后的排队结果。
共有8个人参加排队。编号为3和4的两个人为幼儿，年龄分别为6岁和5岁。编号为5 、21和13的三个人为老人，年龄分别为62岁、60岁和62岁。根据排队规则，老人和幼儿排在其他人的前面，而幼儿又排在老人的前面，所以先排编号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国今年风调雨顺，百姓丰衣足食。为了奖励他那帮管理有方的大臣，他决定把全部的N元奖金平均分配给其中的K位大臣，但酷爱数学的国王要求这K位大臣每人拿到的奖金必须是个素数。哪个大臣能够解决这个数学问题，国王就把奖金给这个大臣和另外的K-1人。
大臣们都想自己获得更多的奖金，所以希望分得奖金的大臣人数K越少越好。机智的大臣请来了“编程大侠”来帮忙解决这个问题。国王的间谍得知了这个情况后向国王汇报了大臣的行为。国王早就听说“编程大侠”的厉害，于是决定问T次这个问题，来试探一下“编程大侠”的真正实力。
【输入数据】
输入文件king.in：输入从文件中读取，输入共T+1行。
第1行一个整数T，表示国王问了T次。
接下来T行每行一个整数N，表示国王打算分配给大臣的总奖金。
【输出数据】
输出文件king.out：结果输出到文件中，输出共T行。
第i行一个整数K，表示最少多少位大臣来平分输入中对应的全部奖金。如果找不到满足国王要求的分配办法，请输出“0”（输出时不包含双引号）。
国王共问了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
4. 修建高楼(build.pas)
【问题描述】
C市有一条东西走向的“市河”。C市的市长打算在“市河”的其中一条岸边自东往西的n个位置（可以将这n个位置看成在一条直线上，且位置不会重叠）依次建造高楼。
C市的设计部门设计了T个方案供市长挑选（方案编号为1到T）。每个方案都提供了建造的每幢高楼的高度，自东向西依次为h1，h2，h3，…，h n-1，h n。每幢楼房的高度在1到n之间（包括1和n），且各不相同。
市长在挑选设计方案时，喜欢n幢高楼中任意3幢（包括不连续的3幢）有一定的“梯度美”。所谓“梯度美”是指这3幢高楼满足：第j幢的高度h j-第i幢的高度h i=第k幢的高度h k-第j幢的高度h j (1≤i < j < k ≤n)。
市长喜欢方案中这种“梯度美”现象越多越好。请编程帮市长挑选一下设计方案吧。
【输入数据】
输入文件build.in：输入从文件中读取，输入共T+1行。
第一行两个整数T和n，分别表示设计部门提供的方案总数和打算建造的高楼数。
接下来每一行表示一种方案。第i+1行表示第i种方案，每行n个整数，依次表示每幢高楼打算建造的高度。
【输出数据】
输出文件build.out：结果输出到文件中，输出共1行。
包含两个整数，第一整数为出现“梯度美”次数最多的方案，第二个整数为对应方案“梯度美”出现的次数。如果出现“梯度美”次数最多的方案有多个，输出方案编号较小的方案。
