2013年第28届宁波市信息学复赛初中组题目.pdfVIP

宁波市第 28 届中小学生计算机程序设计竞赛复赛试题（初中组）第 1 页 共 6 页 宁波市第28届中小学生计算机程序设计竞赛 复赛试题（初中组） 比赛时间：2013年4月13日上午9:00—12:00 题目一览 试题名称 朋友 分数统计 跳棋 迷宫大门 英文代号 friend score jump door 程序名 friend.cpp/pas/c score.cpp/pas/c jump.cpp/pas/c door.cpp/pas/c 输入文件名 friend.in score.in jump .in door.in 输出文件名 friend.out score.out jump .out door.out 内存限制 256MB 256MB 256MB 256MB 时限 1S 1S 1S 1S 注意： 一、 关于竞赛中编程语言使用的规定参照中国计算机学会公布的《关于NOI系列赛编程语言使 用限制的规定》。 二、 评测环境为windows。 宁波市第 28 届中小学生计算机程序设计竞赛复赛试题（初中组）第 2 页 共 6 页 1. 朋友 【题目描述】 经过六年的努力，小明终于被一所知名中学录取。优秀的小明总是对一些奇奇怪怪的事 情感兴趣，这次他想知道谁在这所新学校拥有的朋友最多，由于大家都才刚报到，所以小明 只知道大家两两之间是否是朋友关系。 【输入】 输入文件friend.in的第一行有两个整数n和m，n表示总人数，m表示总关系数。 接下来n行，每行有2个以空格隔开的整数a和b，表示a和b是朋友，a和b均为1到n之间 的整数。不会给出重复的朋友关系。 【输出】 输出文件friend.out 中仅有一行，表示朋友数最多的人所拥有的朋友，每两个整数之间 用空格隔开，按照字典序从小到大输出。如果存在多个人朋友数都是最多的情况，请输出字 典序最小的那人的答案，具体见样例。 【样例输入】 3 3 1 2 2 3 1 3 【样例输出】 2 3 【样例说明】 1、2、3均拥有2个朋友，因此输出字典序较小的1的朋友即可。 1的朋友为2和3，按照字典序从小到大输出，数字之间用空格隔开。 【数据规模】 50%的数据，1 = n = 10 80%的数据，1 = n = 1000 100%的数据，1 = n = 10000，m = 500000 宁波市第 28 届中小学生计算机程序设计竞赛复赛试题（初中组）第 3 页 共 6 页 2. 分数统计 【题目描述】 在统计完朋友情况之后，小明又对大家的毕业学校产生兴趣，但是他觉得单纯的统计人 数是一件非常无聊的事情，于是他设计了一个算法，同一所学校毕业的学生，第1个将获得1 分，第2个获得2分，第3个获得4分…，第i个将获得2i-1分，总分就是这所小学的得分，小明 想知道得分最高的学校有多少分。 【输入】 输入文件score.in的第一行有两个整数n和m，n表示总人数，m表示已知的同校关系数 量。 接下来n行，每行有2个以空格隔开的整数a和b，表示a和b是来自同一所学校，a和b均 为1到n之间的整数。不会给出重复的信息。 【输出】 输出文件 score.out 只有一行，为所有学校中的最高得分。最后得分可能会很大，你只 需要输出后100 位即可，不足100 位的请直接输出。 【样例输入】 5 3 1 2 3 4 1 3 【样例输出】 15 【样例说明】