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

2014年衢州市第二十七届青少年信息学竞赛复赛试卷_提高组

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

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

衢州市第二十七届青少年信息学竞赛复赛试卷

提高组

(请选手务必仔细阅读本页内容)

二.提交源程序文件名

三.编译命令(不包含任何优化开关)

注意事项:

1、文件名(程序名和输入输出文件名)必须使用英文小写。

2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、统一评测时采用的机器配置为:CPU P4 3.0GHz,内存 2G,上述时限以此配置为准。 4、特别提醒:评测在Windows下进行,评测软件为cena8.0。

第 1 页 共 6 页

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

修补管道

(pipe.pas/c/cpp)

【题目描述】

大陆被分成n*m的格子,两个城市M和Z之间的天然气通过管道相连,管道有以下几种形态:

天然气从城市M运送到城市Z,管道是双向的,且对于Block +,天然气必须在两个方向都有流动。如图:

现在有一个格子的管道消失了,你的任务就是找到这个格子以及管道的类型。

【输入格式】

第一行两个数n,m,中间用一个空格隔开;以下 n行,每行m个字符。

'.'表示空格,'|','-','+','1','2','3','4'表示管道的类型。

M、Z表示起点和终点。

数据保证只有一个管道口和M、Z相邻,这个管道设计中没有废弃管道(也就是说所有管道都必须使用),数据保证答案存在且唯一。

【输出格式】

一行,前两个数表示管道位置,后一个字符表示管道类型。

即(行,列,管道类型),中间用一个空格隔开。

【样例输入1】

3 7

.......

.M-.-Z.

.......

【样例输出1】

2 4 -

【数据规模】

对于100%的数据:1≤n,m≤25;

第 2 页 共 6 页 【样例输入2】 3 5 ..1-M 1-+.. Z.23. 【样例输出2】 2 4 4

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

跳跃

(jump.pas/c/cpp)

【题目描述】

跳跃是笨笨的天性,当然跳需要消耗能量,每跳1米就会消耗1点能量,如果笨笨有很多能量就能跳很高。

笨笨为了收集能量,来到百亩森林的一个神秘地方。在这里,笨笨的正上方每100米处就有一个能量球(也就是这些能量球位于海拔100,200,300……米处),每个能量球所能提供的能量是不同的,一共有N个能量球(也就是最后一个能量球在N×100米处)。笨笨为了想收集能量,想跳着吃完所有的能量球。笨笨可以自由控制他每次跳的高度,接着他跳起把这个高度以下的能量球都吃了,他便能获得能量球内的能量,接着吃到的能量球消失。当然笨笨的跳跃技能还不够高,还不会二级跳,所以不能因新吃到的能量而变化此次跳跃的高度,并且每次跳完都会掉下来,回到地面。

问笨笨若要吃完所有的能量球,最多还能保留多少能量。

【输入格式】

输入文件第1行包含两个正整数N,M,表示了能量球的个数和笨笨的初始能量。

第2行包含N个非负整数,从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含的能量,每2个整数之间用1个空格隔开。

【输出格式】

输出文件仅包括一个非负整数,为笨笨吃完所有能量球后最多保留的能量。

【样例输入】

3 200

200 200 200

【样例输出】

400

【样例说明】

第1次跳100米,得到200能量,消耗100能量,所以落地后拥有300能量。

第2次跳300米,吃到剩下的第2棵能量球,消耗拥有的300能量,得到400能量。

若第1次跳200米,第2次跳300米,最后剩余300能量。

【数据规模】

对于10%的数据:有N≤10;

对于20%的数据:有N≤100;

对于40%的数据:有N≤1,000;

对于70%的数据:有N≤100,000;

对于100%的数据:有N≤2,000,000;

保证对于所有数据,笨笨都能吃到所有的能量球,并且能量球包含的能量之和不超过231-1。

第 3 页 共 6 页

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

叠箱子

(box.pas/c/cpp)

【题目描述】

笨笨有N个重量为1的无盖空箱子,每个箱子有长和宽,那么长宽小的箱子就可以放进长宽大的箱子里。现在笨笨要通过把箱子放进其他箱子中来制造一个最重的箱子,请你告诉笨笨一个箱子最多能有多少重。

假设箱子i的长为Ai,宽为Bi。那么箱子i能放进箱子j的条件就是Ai<Aj而且Bi<Bj(如果Ai<Bj

而且Bi<Aj,那么箱子j是不能放进箱子i的)。箱子i、j不能同时放进箱子k中;但是如果箱子i放进箱子j,箱子j又放进箱子k是可以的。 【输入格式】

第一行1个整数N,表示箱子个数。

之后N行,每行2个整数Ai、Bi,表示箱子的长宽。 【输出格式】

一个整数,表示最重的箱子的重量。

【样例输入1】 4 9 10 10 9 1 8 0 0

【样例输出1】 3

【样例输入2】 7 1 2 2 4 2 5 3 3 4 5 5 4 6 5

【样例输出2】 4

【数据规模】

对于10%的数据: 1≤N≤10; 对于40%的数据: 1≤N≤1,000;

对于100%的数据: 1≤N≤500,000; 0≤Ai,Bi≤1,000,000;

神奇的项链

(fett.pas/c/cpp)

【题目描述】

笨笨有一条神奇的项链,为什么说它神奇呢?因为它有两个性质:

1. 神奇的项链可以拉成一条线,线上依次是N个珠子,每个珠子有一个能量值Ei; 2. 除了第一个和最后一个珠子,其他珠子都满足Ei=(Ei-1+Ei+1)/2+Di。

第 4 页 共 6 页

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

由于这条项链很长,我们只能知道其两端珠子的能量值。并且我们知道每个珠子的Di是多少。请聪明的你求出这N个珠子的能量值分别是多少。

【输入格式】

第一行三个整数N、E1、EN,表示珠子个数N,第一个珠子和第N个珠子的能量值。

第二行N-2个整数,表示第2个珠子到第N-1个珠子的Di。

【输出格式】

输出仅一行,N个整数,表示1到N个这N个珠子各自的能量值Ei。每2个整数之间用1个空格隔开;请放心,数据保证对于任意珠子满足(Ei-1+Ei+1)Mod 2=0;

【样例输入1】

4 1 4

0 0

【样例输出1】

1 2 3 4 【样例输入2】 10 1 29 0 2 -3 5 1 4 2 -1 【样例输出2】 1 13 25 33 47 51 53 47 37 29

【数据规模】

对于40%的数据: 1<N≤100;

对于70%的数据: 1<N≤5,000,所有数据(包括计算中的)不超过109;

对于100%的数据: 1<N≤500,000; |E1|、|EN|≤1015;|Di|≤104;

Ships

(ships.pas/c/cpp)

【题目描述】

告诉你一个n*n的正方形。正方形里只有0和1。问你由1组成的不同大小的极大4连通块(有公共边)分别有多少。

【输入格式】

第一行一个整数n表示正方形的大小(左上角为(1,1))。

接下来n行,每行有一些用','分隔的区间,表示在该行上哪些区间值为1。以';'结束。对于每个区间的描述,如果区间的大小为1,那么仅用一个数字表示。如果区间大小大于1,那么用"st-en"描述。st为区间开始的列号。en为区间结束的列号。-为分隔符。

【输出格式】

输出含有若干行。你应该按照连通块的大小降序输出。对于每一行,你需要输出两个整数a,b,分别表示连通块的大小和这种大小的连通块的个数,a,b之间用1个空格隔开。

第 5 页 共 6 页

衢州市第二十七届青少年信息学竞赛复赛试卷(2014) 提高组

【样例输入】

12

2-4,7,9;

1,4,11-12;

1,4,10,12;

1,4-8,10-12;

1,8;

1,3-6,8,10-12;

1,3,5-6,8,11;

1,8,10-12;

1-8;

;

2;

2-4,7-10,12;

【样例输出】

29 1

7 3

4 2

1 3

【数据规模】

保证只有不超过1,000个连通块。保证每个连通块大小不超过1,000;

对于30%的数据:1≤n≤2,000;

对于100%的数据:1≤n≤30,000;

第 6 页 共 6 页

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