第35届全国青少年信息学奥林匹克竞赛（NOI 2018）第二试真题（PDF版,无答案）

全国青少年信息学奥林匹克竞赛
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
每个测试点时限20秒
8.0秒
10.0秒
内存限制
512MB
512MB
512MB
测试点/包数目
20
20
20
测试点是否等分是
是
是
提交源程序文件名
对于C++语言
dragon.cp
center.
cpp
polygon.
cpp
对于C语言
dragon.
c
center.
c
polygon.
C
对于
Pascal语言
dragon.
pas
center.
pas
polygon.
pas
编译选项
对于C++语言
02-1m
对于C语言
02-1m
对于
Pascal语言
-02
注意事项:
1、提交的源文件必须存放在已建立好的下发样例的文件夹中(该文件夹与试题同名)。
2、文件名(包括程序名和输入输出文件名)必须使用英文小写。
3、结果比较方式为忽略行末空格、文末回车后的全文比较。
4、C/C++中函数main(的返回值类型必须是int,值为0。
全国青少年信息学奥林匹克竞赛
第二试屠龙勇士(
dragon)
屠龙勇士(
dragon)
【题目描述】
小D最近在网上发现了一款小游戏。游戏的规则如下:
游戏的目标是按照编号1-n顺序杀掉n条巨龙,每条巨龙拥有一个初始的生命
值a;。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每
次增加p;,直至生命值非负。只有在攻击结束后且当生命值恰好为0时它才会
死去。
游戏开始时玩家拥有m把攻击力已知的剑,每次面对巨龙时,玩家只能选择
把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。
小D觉得这款游戏十分无聊,但最快通关的玩家可以获得ION2018的参赛资格,
于是小D决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则
每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻
击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作
为武器。
●机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的x次,使
巨龙的生命值减少x×ATK。
之后,巨龙会不断使用恢复能力,每次恢复p;生命值。若在使用恢复能力前或
某一次恢复后其生命值为0,则巨龙死亡,玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小D现在得知
了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数x设置为多少,
才能用最少的攻击次数通关游戏吗?
当然如果无论设置成多少都无法通关游戏,输出-1即可。
【输入格式】
从文件
dragon.,in中读入数据。
第一行一个整数T,代表数据组数。
接下来T组数据,每组数据包含5行。
每组数据的第一行包含两个整数,n和m,代表巨龙的数量和初始剑的数量
接下来一行包含n个正整数,第i个数表示第i条巨龙的初始生命值
接下来一行包含n个正整数,第i个数表示第i条巨龙的恢复能力p;
●接下来一行包含n个正整数,第i个数表示杀死第i条巨龙后奖励的剑的攻击
力
接下来一行包含m个正整数,表示初始拥有的m把剑的攻击力。