当前位置:首页 >> 学科竞赛 >>

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


相关文章:
2013安徽省信息学竞赛试题(小学组)
2013安徽省信息学竞赛试题(小学组)_五年级其它课程_其它课程_小学教育_教育专区。2013 年安徽省青少年信息学奥林匹克竞赛 小学组试题 2013 年安徽省青少年信息学奥林...
2010安徽省信息学竞赛(中学组)解题报告
寻宝(truesure) 寻宝( )安徽 芜湖 2010.4.27 2010 年安联杯安徽省青少年信息学奥林匹克竞赛 中学组试题 经过辛勤的工作,墓道终于清理干净,小可可随考古队进入了...
2011小学生信息学竞赛试题
2011小学生信息学竞赛试题_学科竞赛_小学教育_教育专区。中山市第三届小学生信息...2011安徽省信息学竞赛试... 7页 2下载券 喜欢此文档的还喜欢 小...
2011年安庆市信息学(小学组)竞赛解题报告
(只考虑长度,不考虑高与宽) ,现在想把这些橡皮泥块切割安徽 安庆 2011.3.27 6 2011 年安庆市青少年信息学奥林匹克竞赛 上机试题 成 k 块长度相同的小橡皮泥...
2012年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题
2012年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题_学科竞赛_小学教育_教育...2010年安联杯安徽省青少... 5页 免费 2011年安联杯安徽省青少... 暂无评价...
2014年阜阳市中学组信息奥赛试题
2014 年全省青少年信息学奥林匹克竞赛阜阳赛区选拔赛中学组试题(2014 年 3 月 30 日星期日下午 2:30——5:30)题目概况: 题目名称 程序名称 输入文件名 输出...
2011年安徽省中学生生物学竞赛预赛试卷及答案
2011安徽省中学生生物学竞赛预赛试卷及答案_学科竞赛_高中教育_教育专区。2011安徽省中学生生物学竞赛预赛试卷 注意事项:1、本试卷共 100 题,全部为不定向选...
2011年全国高中数学联赛安徽省预赛试题及答案
百度文库 教育专区 高中教育 学科竞赛专题推荐...​数​学​联​赛​安​徽​省​预...命题工作是由安徽省数学会负责,预赛试题所涉及的知识...
2011河南省信息学竞赛试题(初中组)
2011 年河南省青少年信息学(计算机)奥林匹克赛竞赛 年河南省青少年信息学(计算机) (初中组) 初中组)题目名称 提交程序 输入文件 输出文件 各题分值 时限 集合 t...
2011年安徽省中学生生物学竞赛预赛试卷及答案
O 型 3 2011安徽省中学生生物竞赛试题及答案 54、古生物学研究中,骨骼化石是发现和研究最多的部分,请根据以下骨骼描述判断具备此 种骨骼的生物和现存生物的哪...
更多相关标签:
2017安徽省信息学竞赛 | 安徽省信息学竞赛 | 2016安徽省信息学竞赛 | 高中信息学竞赛试题 | 信息学竞赛试题 | 小学信息学竞赛试题 | 中学生信息学竞赛 | 安徽省中考试题 |