tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

2011安徽省信息学竞赛试题(中学组)


2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

2011 年安联杯安徽省青少年信息学奥林匹克竞赛 中学组试题

AOI 2011
比赛时间:2011 年 4 月 16 日 8:00 至 12:00 题目名称 源文件名 输入文件名 输出文件名 试题类型 满分 是否有部分分 时限 内存限制 迷宫密

码 sum.pas/c/cpp sum.in sum.out 传统型 100 否 1秒 128M 重重机关 maze.pas/c/cpp maze.in maze.out 传统型 100 否 1秒 128M 开心农场 farm.pas/c/cpp farm.in farm.out 传统型 100 否 1秒 128M 武林大会 match.pas/c/cpp match.in match.out 传统型 100 否 1秒 128M

注意事项 1. 务必看清题目,严格按照所要求的格式输入、输出。 2. 在调试程序时请先使用题目中的示例数据,然后再自行设计多组测试数据 进行调试。 3. 测试有严格的时间限制,请尽可能优化算法。 4. 命名规则: (1)每题都规定了该题的英文名称。 (2)程序文件和数据文件的主文件名都是该题的英文名字。 (3)程序文件扩展名采用语言环境的默认扩展名。 (4)数据文件都是文本文件,输入和输出文件的扩展名分别是.in 和.out。 5. 程序应从输入文件读取数据,并严格地按照规定的输出格式将结果输出到 输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中,由 于程序所在目录是不确定的,因此不允许在程序中含有盘符信息和任何形 式的路径信息。 6. 选手在竞赛结束时应在 D 盘根目录下建立以参赛号命名的文件夹,并将所完 成各题的源程序文件放到该文件夹中。测试以评测组编译的可执行文件为 准,测试系统使用的是标准的编译指令处理源程序,没有附加任何编译选 项,请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。

安徽

安庆

2011.4.16

1

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

题目 1. 迷宫密码(sum)
猪无戒将蓝兔关在了一座迷宫里。虹猫来到紧闭的迷宫大门前,发现需要 输入密码才能将大门打开。守门人告诉他密码就隐藏在门旁的一个方形木盘 中。方形木盘中有 M 行 N 列格子,每个格子中刻有一个数字,虹猫需要选择一个 数字之和最大的长方形区域来开启迷宫大门。虹猫应该怎么做呢?

1 1 2 3 4 5 -1 -3 -3 4 -3

2 -2 -2 -4 -5 -2

3 -3 2 3 3 -1

4 -4 4 5 6 0

输入:共 M+1 行,第一行为正整数 M(1≤M≤500)和 N《1≤N≤500) (中间用空 格隔开) ,表示木盘上有 M 行 N 列的格子。接下来的 M 行,每行有 N 个整 数(中间用空格隔开),表示格子中的数字,取值范围是[-500,500]。

输出:一个整数,表示数字之和最大的长方形区域内的数字和。

样例: 输入(sum.in): 5 4 -1 -2 -3 -4 -3 -2 2 4 -3 -4 3 5 4 -5 3 6 -3 -2 -1 0 输出(sum.out): 23

安徽

安庆

2011.4.16

2

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

限制: 50%的数据,1≤M≤50,1≤N≤50 90%的数据,1≤M≤100,1≤N≤100 100%的数据,1≤M≤500,1≤N≤500

2. 重重机关(maze)
虹猫终于开启了迷宫的大门,守门人告诉虹猫迷宫里没有水和食物,因此 虹猫必须以最快的速度救出蓝兔。守门人还把迷宫的一些情况告诉了虹猫。这 座迷宫共有 N 个密室,入口密室编号为 1,蓝兔所在的密室编号为 N。各密室之 间一共有 M 条单向密道。部分密道入口处有机关,这些机关最初是关闭的,一 旦有人进入迷宫,所有机关就会按照预先设定的各自的时间间隔 S 和 C 循环关闭 和开启。如果进入某条密道时恰好该密道入口处的机关处于开启状态,就会被 机关困住,需要一定时间 E 才能挣脱机关继续前进。 除 N 号密室外,迷宫的所有地面都无法停留,否则地面就会陷落,虹猫只 能马不停蹄地一直往前走。设虹猫进入迷宫的时刻为 0,N 个密室的通过时间可 以忽略不计,通过密道则需要一定的时间 T,请你帮助虹猫用最短的时间到达 N 号密室救出蓝兔。

2
1(3,2,2) 2(3,0,3) 3(0,1,5)

1

4

5(4,2,6)

6(2,1,7)

3
N=4,M=5;有向边上标示的数字分别表示T(S,C,E)。
输入:共 M+1 行,第一行为正整数 N 和 M(中间用空格隔开) (1≤N≤10000,1 ≤M≤1000000) ,分别表示密室的数量和密道的数量。接下来共 M 行,每 行有 6 个整数(中间用空格隔开),分别是 U、V、T、S、C、E,其中 U、
安徽 安庆 2011.4.16 3

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

V 表示该条密道由密室 U 通往密室 V(1≤U、V≤N);T 表示通过该密道 需要 T 分钟(1≤T≤200);S 和 C 表示密道入口机关在有人进入迷宫 S 分钟后开启,保持开启状态 C 分钟后关闭,然后保持关闭状态 S 分钟后再 度开启,循环往复(0≤S、C≤200,且 S、C 不同时为 0);E 表示一旦被 机关困住,需要 E 分钟才能挣脱机关继续前进(1≤E≤600)。 以下面的一行输入数据为例: 3 4 6 2 1 7 表示该密道从 3 号密室连接到 4 号密室,通过该密道需要 6 分钟,在有人进 入迷宫后,该密道入口的机关在[0,2)时间区间为关闭状态 (如果时刻 t 在 [a,b) 时间区间,则有 a≤t<b),[2,3)时间区间为开启状态,[3,5)时间区间为关闭 状态,循环往复。也就是说,如果虹猫在 2 分(含 2 分)到 3 分(不含 3 分)之 间进入该密道,此时机关恰好是开启状态,他会被机关困住,需 7 分钟才能挣 脱;而如果他在 3 分(含 3 分)到 5 分(不含 5 分)之间进入密道,则此时机关 恰好是关闭状态,不会被机关困住。

输出:一个正整数,表示虹猫到达 N 号密室的最短时间(单位:分钟)。

样例: 输入(maze.in): 4 5 1 2 1 3 2 2 1 3 5 4 2 6 2 1 2 3 0 3 2 4 3 0 1 5 3 4 6 2 1 7

输出(maze.out) 9

安徽

安庆

2011.4.16

4

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

限制: 40%的数据,N≤100,M≤1000 100%的数据,N≤10000,M≤1000000 所有数据保证 1 号密室到 N 号密室连通。

3. 开心农场(farm)
虹猫成功救出蓝兔后,为了帮助蓝兔摆脱心理阴影,和蓝兔一起玩起了开 心农场的游戏。这个游戏开始时有一个体验期,系统会分配给玩家一定数量的 金币。规定在同一时期只能种植一种作物, 但是只要金币允许,玩家可以在土地 上种植任意多的同一种作物。种子需要一定费用,作物一旦成熟玩家就收获并 售出作物。系统将根据玩家在体验期结束时所拥有的金币数量给予相应奖励 (如 果作物在体验期结束的时刻尚未成熟,则不计入在内) 。农场中的作物有的在体 验期内全时段开放种植,而有的则只能在某个时段种植。每种作物播种以后需 要经过一定的时间才会成熟,而播种、收获的时间可以忽略不计。虹猫是个爱 思考的孩子,他想在体验期内获得最多的金币,应该怎么做呢?

输入:共 K+1 行, 第一行有 3 个正整数 M、D 和 K,分别用一个空格隔开,其中 M 表示游戏开始时所拥有的金币数量(1≤M≤200),D 表示体验期的时长 (1≤D≤10000,单位:小时),K 表示作物的种类数(1≤K≤5000)。 接下来 K 行,每行有 5 个用空格隔开的非负整数,分别是 S、F、T、B、 E,其中 S 表示该作物的种子单价(1≤S≤100),F 表示该作物的售出价 格(S≤F≤1000),T 表示该作物成熟需要的时间(1≤T≤100,单位: 小时),B 和 E 分别表示该作物可以种植的开始时间和结束时间(即若当 前时刻为 t,且 Bi≤t<Ei,则此时第 i 种作物可以播种,且其成熟时间 可在 Ei 时刻以后,1≤i≤K;B、E 单位为时,0≤B≤D,B<E≤10000) 。

输出:一个正整数,表示体验期结束时虹猫能够拥有的最多金币数。

样例:
安徽 安庆 2011.4.16 5

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

输入(farm.in): 11 2 2 10 15 1 0 2 12 20 1 0 2

输出(farm.out): 24

限制: 40%的数据,D≤100,K≤10 100%的数据,D≤10000,K≤5000

4. 武林大会(match)
虹猫和好朋友们组队参加武林大会,最终的决赛在他和猪无戒的参赛组之 间展开。比赛规则如下:两个组都必须出 N 个选手,每个选手必须与对方组的 一个选手进行一场比赛,且只能进行一场比赛。经过对本组组员和对方组员使 用的武器和武功的分析,虹猫得出了自己组中的每个成员与对方组员比赛时的 取胜概率 pij%(其中 pij 为非负整数,0≤pij≤100,1≤i,j≤N)。虹猫经过细心的 计算,发现了一种对阵方式,能使得虹猫组的平均取胜概率最大,其中平均取 胜概率为某种对阵方式下,虹猫组所有组员取胜概率之和的平均值向下取整 (例 如,73.635 向下取整的值为 73)。你知道虹猫是怎么做的吗?

输入:共 N+1 行, 第一行为正整数 N (1≤N≤200) ,表示每个组的参赛队员数。 接下来 N 行,每行有 N 个不大于 100 的用空格隔开的非负整数,其中第 i 行的第 j 个数字表示虹猫组的第 i 个组员对猪无戒组的第 j 个组员的取胜 概率 pij%( 0≤pij≤100,1≤i,j≤N)。

输出:一个正整数,表示虹猫组的最大平均取胜概率。

安徽

安庆

2011.4.16

6

2011 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

样例: 输入(match.in): 4 40 50 30 70 80 30 40 70 50 60 70 80 90 10 20 30

输出(match.out): 70

限制: 20%的数据,1≤N≤8 60%的数据,1≤N≤15 100%的数据,1≤N≤200

安徽

安庆

2011.4.16

7


推荐相关:

2010年安徽省青少年信息学奥林匹克竞赛试题

80页 免费 2011安徽信息学竞赛(小学... 6页 免费2​0​1​0​年​...中学组试题 题目名称 源文件名 输入文件 名 输出文件 名 试题类型 满分 是否有...


2011河南省信息学竞赛试题(初中组)

2011河南省信息学竞赛试题(初中组)_IT/计算机_专业资料。2011河南省信息学(计算机)奥林匹克竞赛(初中组) t1 集合 t2 骨牌 t3 车队过桥 t4 字符串序号2011...


1999年—2011年信息学奥赛提高组初赛试题PASCAL(附答案_完整)1

1999年—2011信息学奥赛提高组初赛试题PASCAL(附答案_完整)1_学科竞赛_高中...⑦ ; CCF NOIP2011 初赛 普及组 Pascal 13 江苏省新海高级中学 第十六届全国...


2010年安徽省中学生生物竞赛试题

2010年安徽省青少年信息学... 5页 2财富值 2010年...陕西省宝鸡市2011届高三教... 15页 5财富值 张瑞敏...年安徽省中学生生物竞赛试题一、细胞生物学、生物化...


第十七届全国青少年信息学奥林匹克联赛初赛试题

第十七届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_高中教育_教育专区。第...) + 1]) - CCF NOIP2011 普及组(Pascal 语言)参考答案与评分标准一、单项...


NOIP2011第十七届初赛Pascal普及组试题与答案(Word)

NOIP2011第十七届初赛Pascal普及组试题与答案(Word)_学科竞赛_初中教育_教育专区。第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 ●● Pascal 语言 两...


第十七届2011全国青少年信息学奥林匹克联赛初赛试题(普及组C++)

第十七届2011全国青少年信息学奥林匹克联赛初赛试题(普及组C++)_学科竞赛_高中...第十七届全国青少年信息学奥林匹克联赛初赛试题( 普及组●● C++语言 二小时完成...


2011年金华市第二十届小学信息学竞赛试卷-pascal

2011 年金华市第 20 届信息学竞赛试题(小学组·2011 年 10 月 15 日)·金华一中·第 2 页(共 4 页) 三、阅读程序,写结果(6 分/题*4 题,共 24 分...


1999年至2013年历年信息学奥赛提高组初赛答案

年历年信息学奥赛提高组初赛答案_学科竞赛_高中教育_...福建省莆田第一中学 信息学奥赛兴趣小组 整理:林梓...(2011)信息学奥赛提高组初赛试题答案一、单项...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com