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


推荐相关:

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

2011年安徽青省年信息学奥赛小学组试卷2011年安徽青省年信息学奥赛小学组试卷隐藏>> 2011 年安联杯安徽省青少年信息学奥林匹克竞赛 小学组试题 2011 2011 年安联杯...


2013安徽省信息学竞赛试题(小学组)

2013安徽省信息学竞赛试题(小学组)_五年级其它课程_其它课程_小学教育_教育专区。2013 年安徽省青少年信息学奥林匹克竞赛 小学组试题 2013 年安徽省青少年信息学奥林...


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

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


2011年安庆市信息学(小学组)竞赛解题报告

(只考虑长度,不考虑高与宽) ,现在想把这些橡皮泥块切割安徽 安庆 2011.3.27 6 2011 年安庆市青少年信息学奥林匹克竞赛 上机试题 成 k 块长度相同的小橡皮泥...


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

2011 年河南省青少年信息学(计算机)奥林匹克赛竞赛 年河南省青少年信息学(计算机) (初中组) 初中组)题目名称 提交程序 输入文件 输出文件 各题分值 时限 集合 t1...


2011年阜阳市中学生信息学奥林匹克竞赛

FYOI2011 中学组 安徽省青少年信息学奥林匹克竞赛 信息学奥林匹克竞赛阜阳赛区 2011安徽省青少年信息学奥林匹克竞赛阜阳赛区 选拔赛中学组试题 选拔赛中学组试题 ...


2010安徽省信息学竞赛试题(小学组)

2010安徽省信息学竞赛(中学... 9页 5财富值 2011安徽省信息学竞赛试题... ...2010 年安联杯安徽省青少年信息学奥林匹克竞赛 小学组试题 2010 年安联杯安徽省...


2011小学生信息学竞赛试题

2011小学生信息学竞赛试题_学科竞赛_小学教育_教育专区。中山市第三届小学生信息...2011安徽省信息学竞赛试... 7页 2下载券 喜欢此文档的还喜欢 小...


2011年安徽省中学生生物学竞赛预赛试卷及答案

2011安徽省中学生生物学竞赛预赛试卷及答案_学科竞赛_高中教育_教育专区。2011 ...下列行为中属于传递信息的是( A. 雌蛾分泌性激素 D. 公鸡的争斗就是一个...


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

2012年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题_学科竞赛_小学教育_教育...2010年安联杯安徽省青少... 5页 免费 2011年安联杯安徽省青少... 暂无评价...

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