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

宁波市第 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 样例说明 1 2 3 4来自同一所学校 该所学校所得的分数为1 2 4 8 15 数据规模 60 的数据 1 n 10 80 的数据 1 n 70 100 的数据 1 n 10000 1 m 100000 宁波市第 28 届中小学生计算机程序设计竞赛复赛试题 初中组 第 4 页 共 6 页 3 跳棋跳棋 题目描述 小明迷恋上了一个新的跳棋游戏 游戏规则如下 棋盘是一排从0开始 顺序编号的格子 游戏开始时你位于0号格子 你每次只能往编号大的格子跳 而且你每次至少需要跳过L个格 子 至多只能跳过R个格子 每个格子都有一个给定的伤害值 显然你希望得到的伤害值越 少越好 你能告诉小明他当他跳到最后一个格子时受到的累积伤害值最小为多少吗 如果无论如何小明都无法跳到最后一个格子 这个时候你需要输出 1 注 从i号格子跳过x个格子表示从i号格子跳到第i x 1号格子 输入 输入文件jump in第一行有三个整数n L和R n表示格子的编号从0到n L和R表示最 少需要跳过的格子数和最多能够跳过的格子数 第二行有n个正整数 两个数字间用空格隔开 表示每个格子的伤害值 输出 输出文件jump out仅有一个整数 表示受到的最小伤害值 保证结果小于maxlongint 样例输入 10 2 6 1 3 5 7 9 2 4 6 8 10 样例输出 12 样例说明 0 1 3 5 7 9 2 4 6 8 10 数据规模 50 的数据 1 n 1000 65 的数据 1 n 10000 100 的数据 1 n 1000000 1 L R n 其中有15 的数据 1 n 1000000 1 L R 10 宁波市第 28 届中小学生计算机程序设计竞赛复赛试题 初中组 第 5 页 共 6 页 4 迷宫大门迷宫大门 题目描述 在跳棋游戏大获全胜后 小明就开始一个人在校园里溜达了 突然他在校园角落里发现 了一面神奇的墙壁 墙壁上有一排钉子 每个钉子上都挂着一根两端系有小球的绳子 如下 图所示 小明可以调整每一根绳子在钉子左右两端的长度 当来自不同绳子的相邻小球高度一样 时 具体可见样例说明 便可获得积分1分 当小明的方案获得最高积分时 迷宫大门就会 开启 小明就可以进去寻找宝藏啦 输入 输入文件door in第一行为一个正整数n 表示墙上的绳子数 接下来n行 每行2个整数a和b 表示绳子左右两端的初始长度 输出 输出文件 door out 仅有一个正整数 表示小明可以获得的最高积分 样例输入 3 1 1 3 2 1 4 样例输出 2 宁波市第 28 届中小学生计算机程序设计竞赛复赛试题 初中组 第 6 页 共 6 页 样例说明 数据规模 序号 分值 n a b 1 5 n 5 a b 5 2 5 n 5 a b 15 3 5 n 20 a b 15 4 5 n 100 a b 109 5 5 n 500 a b 10000 6 5 n 1100 a b 10000 7 5 n 1000 a b 10 8 5 n 3000 a b 109 9 5 n 20000 a b 109 10 5 n 100000 a b 5 11 5 n 1000