9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

2014年安徽省青少年信息学奥林匹克竞赛(中学组)DAY1试题



2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

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

第一试
AOI 2014 (请选手仔细阅读本页内容)
比赛用时(5 小时) 竞赛时间:2014 年 4 月 18 日 8:00-13:00
题目名称 目录 可执行文

件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型 拼图 puzzle puzzle.exe puzzle.in puzzle.out 1秒 256M 10 10 否 传统型 宅男计划 food food.exe food.in food.out 1秒 256M 10 10 否 传统型 骑士游戏 knight knight.exe knight.in knight.out 3秒 256M 10 10 否 传统型

提交源程序须加后缀 对于 Pascal 语言 puzzle.pas 对于 C 语言 puzzle.c 对于 C++ 语言 puzzle.cpp

food.pas food.c food.cpp

knight.pas knight.c knight.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关。

安徽

合肥

2014.4.18 第1页 共7页

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

拼图
【故事背景】 JYY 最近迷上了拼图游戏。作为一个计算机科学家,JYY 有一套黑白色的 拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白 色子矩形。 【问题描述】 JYY 一共有 S 块拼图, 并且由 1 到 S 编号。 编号为 i 的拼图是一个 N 行 的方格矩形,每个方格都为黑色或者白色。 列

一开始 JYY 将他的这 S 块拼图按照编号顺序左右相连依次放在桌上拼成了 一个 N 行 M 列(这里 )的大矩形。 之后 JYY 发现,可以通过改变这 S 块拼图的连接次序,使得拼成的 N 行 M 列的大矩形中,最大全白子矩形面积变大。 现在 JYY 想知道,怎么拼才能得到最大的全白子矩形呢?请你帮助他计算 出最佳的拼接方案。 【输入格式】 从文件 puzzle.in 中读入数据。 每个输入文件中包含多组测试数据。输入文件第一行包含一个整数 T,代表 测试数据的组数,接下来按顺序描述了每组测试数据。 每组测试数据的第一行包含两个整数 S 和 N。 接下来 S 组输入,第 i 组对应编号为 i 的拼图。 在第 i 组输入中,第一行包含一个整数 ; 接下来 N 行描述一个 N 行 列的 0/1 矩形; 其中第 x 行 y 列为 0 则表示该拼图对应位置的颜色是白色,反之则为黑色。 【输出格式】 输出到文件 puzzle.out 中。 对于每组数据输出一行包含一个整数 ans, 表示最大可能的全白色子矩形的面 积。 【样例输入】 1 3 4 4 1001 0000
安徽 合肥 2014.4.18 第2页 共7页

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

0010 1001 3 000 010 000 011 2 00 10 01 00 【样例输出】 6 【样例说明】 最佳方案所最终拼成的大矩形为 000100100 010000010 000001001 011100100 粗体部分是面积为 6 的白色子矩形。 【数据规模与约定】 对于 10%的数据满足 对于 30%的数据满足 对于 50%的数据满足 对于 100%的数据满足 ; ; 。 ;

安徽

合肥

2014.4.18 第3页 共7页

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

宅男计划
【故事背景】 自从迷上了拼图,JYY 就变成了个彻底的宅男。为了解决温饱问题,JYY 不得不依靠叫外卖来维持生计。 【问题描述】 外卖店一共有 N 种食物,分别有 1 到 N 编号。第 i 种食物有固定的价钱 和 保质期 。第 i 种食物会在 天后过期。JYY 是不会吃过期食物的。 比如 JYY 如果今天点了一份保质期为 1 天的食物,那么 JYY 必须在今天或 者明天把这个食物吃掉,否则这个食物就再也不能吃了。保质期可以为 0 天,这 样这份食物就必须在购买当天吃掉。 JYY 现在有 M 块钱,每一次叫外卖需要额外付给送外卖小哥外送费 F 元。 送外卖的小哥身强力壮,可以瞬间给 JYY 带来任意多份食物。JYY 想知道,在 满足每天都能吃到至少一顿没过期的外卖的情况下,他可以最多宅多少天呢? 【输入格式】 从文件 food.in 中读入数据。 第一行包含三个整数 M,F 和 N。 接下来 N 行,第 i 行包含两个整数 和 【输出格式】 输出到文件 food.out 中。 输出仅包含一行一个整数表示 JYY 可以宅的最多的天数。 【样例输入】 32 5 2 5 0 10 2 【样例输出】 3 【样例说明】 JYY 的最佳策略是: 第一天买一份食物 1 和一份食物 2 并且吃一份食物 1;
安徽 合肥 2014.4.18 第4页 共7页



2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

第二天吃一份食物 2; 第三天买一份食物 1 并且吃掉。 【数据规模与约定】 对于 10%的数据满足 对于 30%的数据满足 对于 60%的数据满足 对于 100%的数据满足 ; ; ; 。

安徽

合肥

2014.4.18 第5页 共7页

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

骑士游戏
【故事背景】 长期的宅男生活中,JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会 扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。 【问题描述】 在这个游戏中,JYY 一共有两种攻击方式,一种是普通攻击,一种是法术攻 击。两种攻击方式都会消耗 JYY 一些体力。 采用普通攻击进攻怪兽并不能把怪兽彻底杀死, 怪兽的尸体可以变出其他一 些新的怪兽, 注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪 兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通 攻击, 法术攻击会消耗更多的体力值 (但由于游戏系统 bug, 并不保证这一点) 。 游戏世界中一共有 N 种不同的怪兽,分别由 1 到 N 编号,现在 1 号怪兽入 侵村庄了, JYY 想知道, 最少花费多少体力值才能将所有村庄中的怪兽全部杀死 呢? 【输入格式】 从文件 knight.in 中读入数据。 第一行包含一个整数 N。 接下来 N 行,每行描述一个怪兽的信息; 其中第 i 行包含若干个整数,前三个整数为 , 和 ,表示对于 i 号怪兽, 普通攻击需要消耗 的体力,法术攻击需要消耗 的体力,同时 i 号怪兽死亡后 会产生 个新的怪兽。接下来 个 1 到 N 之间并且不为 i 的整数,表示一个新出 现的怪兽编号。同一编号的怪兽可以出现多个。 【输出格式】
去掉

输出到文件 knight.out 中。 输出一行一个整数,表示最少需要的体力值。 【输入样例】 4 4 3 1 5

27 3 2 3 2 5 1 2 13 2 4 2 6 1 2

安徽

合肥

2014.4.18 第6页 共7页

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题

【输出样例】 26 【样例说明】 首先用消耗 4 点体力用普通攻击,然后出现的怪兽编号是 2,2 和 3。花费 10 点体力用法术攻击杀死两个编号为 2 的怪兽。剩下 3 号怪兽花费 1 点体力进 行普通攻击。此时村庄里的怪兽编号是 2 和 4。最后花费 11 点体力用法术攻击 将这两只怪兽彻底杀死。 一共花费的体力是 4+5+5+1+5+6=26。 【数据规模】 对于 20%的数据满足 对于 50%的数据满足 对 于 100% 的数 据满 足 5×1014。
5乘10的14次方

; ;

安徽

合肥

2014.4.18 第7页 共7页



更多相关文章:
第22届全国青少年信息学奥林匹克联赛NOIP2016提高组试题day1
第22届全国青少年信息学奥林匹克联赛NOIP2016提高组试题day1_学科竞赛_高中教育_教育专区。NOIP2016复赛提高组day1 word版 第22 届全国青少年信息学奥林匹克联赛 CCF...
江苏省青少年信息学奥林匹克竞赛委员会
江苏省青少年信息学奥林匹克竞赛委员会苏信奥委 [...在江苏省泰州中学举行, 现将结果公布如下: 1、...执业医师实践技能考试模拟试题 89份文档 应届生求职...
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_...第22 届全国青少年信息学奥林匹克联赛 CCF-NOIP-...提高组(复赛) 第一试竞赛时间: 2016 年 11 月 ...
NOIP 2016 提高组 复赛 Day1
NOIP 2016 提高组 复赛 Day1_学科竞赛_高中教育_教育专区。第二十二届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组(复赛) 第一试 ...
更多相关标签:
小学奥林匹克信息学    奥林匹克信息学竞赛    青少年信息学奥林匹克    奥林匹克信息学有用吗    奥林匹克信息学    奥林匹克信息学 江苏    奥林匹克信息学试题    国际信息学奥林匹克    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图