haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

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

发布时间:2014-05-30 14:38:59  

宁波市第 28 届中小学生计算机程序设计竞赛复赛试题(初中组)第 1 页 共 6 页

宁波市第28届中小学生计算机程序设计竞赛

复赛试题(初中组)

比赛时间:2013年4月13日上午9:00—12:00

题目一览

注意:

一、 关于竞赛中编程语言使用的规定参照中国计算机学会公布的《关于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

【样例说明】

【数据规模】

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 页 【样例说明】

【数据规模】

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com