PDF《CCF NOI 2018》

全国青少年信息学奥林匹克竞赛 CCF NOI

2018 第二试 时间:2018 年7月20 日08:00 ? 13:00 题目名称 屠龙勇士 情报中心 多边形 题目类型 传统型 传统型 传统型 目录 dragon center polygon 可执行文件名 dragon center polygon 输入文件名 dragon.

in center.in polygon.in 输出文件名 dragon.out center.out polygon.out 每个测试点时限 2.0 秒8.0 秒10.0 秒 内存限制

512 MB

512 MB

512 MB 测试点/包数目

20 20

20 测试点是否等分 是是是提交源程序文件名 对于 C++ 语言 dragon.cpp center.cpp polygon.cpp 对于 C 语言 dragon.c center.c polygon.c 对于 Pascal 语言 dragon.pas center.pas polygon.pas 编译选项 对于 C++ 语言 -O2 -lm 对于 C 语言 -O2 -lm 对于 Pascal 语言 -O2 注意事项:

1、提交的源文件必须存放在已建立好的下发样例的文件夹中(该文件夹与试题同名) .

2、文件名(包括程序名和输入输出文件名)必须使用英文小写.

3、结果比较方式为忽略行末空格、文末回车后的全文比较.

4、C/C++ 中函数 main() 的返回值类型必须是 int,值为 0.

5、对于因未遵守以上规则对成绩造成的影响,相关申诉不予受理. 全国青少年信息学奥林匹克竞赛 第二试 屠龙勇士(dragon) 屠龙勇士(dragon) 【题目描述】 小D最近在网上发现了一款小游戏.游戏的规则如下: ? 游戏的目标是按照编号 1~n 顺序杀掉 n 条巨龙,每条巨龙拥有一个初始的生命 值ai .同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每 次增加 pi ,直至生命值非负.只有在 . 攻.击.结.束.后且当生命值 . 恰.好为

0 时它才会 死去. ? 游戏开始时玩家拥有 m 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一 把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑. 小D觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格, 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则: ? 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中 . 攻.击.力.最.大的一把剑作为武器.如果没有这样的剑,则选择 . 攻.击.力.最.低的一把剑作 为武器. ? 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙 . 固.定.的x次,使 巨龙的生命值减少 x * ATK . ? 之后,巨龙会不断使用恢复能力,每次恢复 pi 生命值.若在使用恢复能力前或 某一次恢复后其生命值为

0 ,则巨龙死亡,玩家通过本关. 那么显然机器人的 . 攻.击.次.数是决定能否最快通关这款游戏的关键.小D现在得知 了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 x 设置为多少, 才能用最少的攻击次数通关游戏吗? 当然如果无论设置成多少都无法通关游戏,输出-1 即可. 【输入格式】 从文件 dragon.in 中读入数据. 第一行一个整数 T ,代表数据组数. 接下来 T 组数据,每组数据包含

5 行. ? 每组数据的第一行包含两个整数,n 和m,代表巨龙的数量和初始剑的数量;

? 接下来一行包含 n 个正整数,第i个数表示第 i 条巨龙的初始生命值 ai ;

? 接下来一行包含 n 个正整数,第i个数表示第 i 条巨龙的恢复能力 pi ;

? 接下来一行包含 n 个正整数,第i个数表示杀死第 i 条巨龙后奖励的剑的攻击 力;

? 接下来一行包含 m 个正整数,表示初始拥有的 m 把剑的攻击力. 第2页共11 页 全国青少年信息学奥林匹克竞赛 第二试 屠龙勇士(dragon) 【输出格式】 输出到文件 dragon.out 中. 一共 T 行. 第i行一个整数,表示对于第 i 组数据,能够使得机器人通关游戏的最小攻击次数 x ,如果答案不存在,输出-1. 【样例