TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5052
  • 题目
  • P5052「NOI2018」屠龙勇士
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 512m
    问题描述

    小 D 最近在网上发现了一款小游戏。游戏的规则如下:

    • 游戏的目标是按照编号 $1$~\(n\) 顺序杀掉 \(n\) 条巨龙,每条巨龙拥有一个初始的生命值 \(a_i\) 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 \(p_i\),直至生命值非负。只有在攻击结束后且当生命值恰好为 $0$ 时它才会死去。
    • 游戏开始时玩家拥有 \(m\) 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。

    小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格, 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

    • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。
    • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 \(x\) 次,使巨龙的生命值减少 \(x \times ATK\)
    • 之后,巨龙会不断使用恢复能力,每次恢复 \(p_i\) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 $0$,则巨龙死亡,玩家通过本关。

    那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 \(x\) 设置为多少,才能用最少的攻击次数通关游戏吗?

    当然如果无论设置成多少都无法通关游戏,输出 \(-1\) 即可。

    输入格式

    从文件 dragon.in 中读入数据。

    第一行一个整数 \(T\),代表数据组数。

    接下来 \(T\) 组数据,每组数据包含 $5$ 行。

    • 每组数据的第一行包含两个整数,\(n\)\(m\),代表巨龙的数量和初始剑的数量;
    • 接下来一行包含 \(n\) 个正整数,第 \(i\) 个数表示第 \(i\) 条巨龙的初始生命值 \(a_i\)
    • 接下来一行包含 \(n\) 个正整数,第 \(i\) 个数表示第 \(i\) 条巨龙的恢复能力 \(p_i\)
    • 接下来一行包含 \(n\) 个正整数,第 \(i\) 个数表示杀死第 \(i\) 条巨龙后奖励的剑的攻击力;
    • 接下来一行包含 \(m\) 个正整数,表示初始拥有的 \(m\) 把剑的攻击力。
    输出格式

    输出到文件 dragon.out 中。

    一共 \(T\) 行。

    \(i\) 行一个整数,表示对于第 \(i\) 组数据,能够使得机器人通关游戏的最小攻击次数 \(x\),如果答案不存在,输出 \(-1\)

    样例输入

    2
    3 3
    3 5 7
    4 6 10
    7 3 9
    1 9 1000
    3 2
    3 5 6
    4 8 7
    1 1 1
    1 1

    样例输出

    59
    -1

    提示

    样例 1 解释

    第一组数据:

    • 开始时拥有的剑的攻击力为 \(\{1,9,10\}\),第 $1$ 条龙生命值为 $3$,故选择攻击力为 $1$ 的剑,攻击 $59$ 次,造成 $59$ 点伤害,此时龙的生命值为 \(-56\),恢复 $14$ 次后生命值恰好为 $0$,死亡。
    • 攻击力为 $1$ 的剑消失,拾取一把攻击力为 $7$ 的剑,此时拥有的剑的攻击力为 \(\{7,9,10\}\),第 $2$ 条龙生命值为 $5$,故选择攻击力为 $7$ 的剑,攻击 $59$ 次,造成 $413$ 点伤害,此时龙的生命值为 \(-408\),恢复 $68$ 次后生命值恰好为 $0$,死亡。
    • 此时拥有的剑的攻击力为 \(\{3,9,10\}\),第 $3$ 条龙生命值为 $7$,故选择攻击力为 $3$ 的剑,攻击 $59$ 次,造成 $177$ 点伤害,此时龙的生命值为 \(-170\),恢复 $17$ 次后生命值恰好为 $0$,死亡。
    • 没有比 $59$ 次更少的通关方法,故答案为 $59$。

    第二组数据:

    • 不存在既能杀死第一条龙又能杀死第二条龙的方法,故无法通关,输出 \(-1\)
    测试点编号 \(n\) \(m\) \(p_i\) \(a_i\) 攻击力 其他限制
    1 \(\le 10^5\) \(=1\) \(=1\) \(\le 10^5\) \(=1\)
    2 \(\le 10^5\) \(=1\) \(=1\) \(\le 10^5\) \(=1\)
    3 \(\le 10^5\) \(=1\) \(=1\) \(\le 10^5\) \(\le 10^5\)
    4 \(\le 10^5\) \(=1\) \(=1\) \(\le 10^5\) \(\le 10^5\)
    5 \(\le 10^3\) \(\le 10^3\) \(\le 10^5\) \(\le 10^5\) \(\le 10^5\) 特性 1、特性 2
    6 \(\le 10^3\) \(\le 10^3\) \(\le 10^5\) \(\le 10^5\) \(\le 10^5\) 特性 1、特性 2
    7 \(\le 10^3\) \(\le 10^3\) \(\le 10^5\) \(\le 10^5\) \(\le 10^5\) 特性 1、特性 2
    8 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    9 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    10 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    11 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    12 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    13 \(=1\) \(=1\) \(\le 10^8\) \(\le 10^8\) \(\le 10^6\) 特性 1
    14 \(=10^5\) \(=10^5\) \(=1\) \(\le 10^8\) \(\le 10^6\) 无特殊限制
    15 \(=10^5\) \(=10^5\) \(=1\) \(\le 10^8\) \(\le 10^6\) 无特殊限制
    16 \(\le 10^5\) \(\le 10^5\) 所有 \(p_i\) 是质数 \(\le 10^12\) \(\le 10^6\) 特性 1
    17 \(\le 10^5\) \(\le 10^5\) 所有 \(p_i\) 是质数 \(\le 10^12\) \(\le 10^6\) 特性 1
    18 \(\le 10^5\) \(\le 10^5\) 无特殊限制 \(\le 10^12\) \(\le 10^6\) 特性 1
    19 \(\le 10^5\) \(\le 10^5\) 无特殊限制 \(\le 10^12\) \(\le 10^6\) 特性 1
    20 \(\le 10^5\) \(\le 10^5\) 无特殊限制 \(\le 10^12\) \(\le 10^6\) 特性 1

    特性 1 是指:对于任意的 \(i\)\(a_i \le p_i\)

    特性 2 是指:\(\operatorname{lcm}(p_i) \le 10^6\),即所有 \(p_i\) 的最小公倍数不大于 $10^6$。

    对于所有的测试点,\(T \le 5\),所有武器的攻击力 \(\le 10^6\),所有 \(p_i\)最小公倍数 \(\le 10^{12}\)

    提示

    你所用到的中间结果可能很大,注意保存中间结果的变量类型。