#P18487. 'Ello, and What Are You After, Then?
'Ello, and What Are You After, Then?
'Ello, and What Are You After, Then?
你正在玩 RunEscape。Slayer 是一项反复完成“击杀某类怪物若干只”任务的活动。你想知道怎样最快训练这项技能。
有 位任务发布者(slayer master)。发布者 可以分配 种任务。对于其中第 种任务,你知道:
- :该任务的抽取频率权重。
- :完成该任务需要的分钟数。
- :执行该任务时每分钟获得的经验值(XP)。完成它共获得 点经验。
每完成一个任务,获得 点 slayer points(任务点数)。获得任务后,也可以支付 点任务点数跳过该任务,不完成它、不获得它的经验,也不花费它的执行时间。
反复执行以下一轮操作:
- 选择一位任务发布者,记其编号为 。
- 屏蔽该发布者的至多 种任务,但必须至少留下一种不被屏蔽。设本轮屏蔽的任务下标集合为 。抽到第 种任务的概率为
- 发布者按这个概率随机分配一个任务。你可以跳过它并失去 点任务点数,也可以完成它并获得该任务的经验和 点任务点数。
- 回到第 1 步,重新选择发布者和本轮屏蔽集合。
你最初有 点任务点数,在整个过程中任务点数不能变为负数。因此点数少于 时不能跳过任务。
求在一切选择都最优的情况下,最大可能的长期期望经验获取速率 ,单位为 XP/分钟。下面的“形式化定义”给出了 的精确含义。
输入格式
第一行三个整数 ,其中 ,。
第二行一个整数 (),表示任务发布者数。
随后依次描述每位发布者。先输入一个整数 (),再输入 行,每行三个整数 ,三者都在 中。
所有发布者的任务种数之和满足 。
输出格式
输出一个浮点数 。
当且仅当输出值 与标准答案 满足
时,认为答案正确。即绝对误差或相对误差不超过 。
原样例 1
输入:
0 1 6
2
1
1 1 1
2
1 10 1
1 10 10
输出:
7.000000000000
原样例 2
输入:
2 1 2
1
4
10 2 1
10 1 1
1 10 1
1 1 10
输出:
5.909090909091
形式化定义
取一个自然数 ,考虑恰好执行 轮操作。一个策略是由 个三元组 组成的序列。第 个三元组描述第 轮的行为:
- :这一轮选择的任务发布者。
- :这一轮屏蔽的任务集合,满足上述屏蔽规则。
- :一个函数 。 表示这一轮恰有 点任务点数时,哪些任务被分配后会被跳过。若 ,必须有 。
这里 是非负整数集合, 表示集合 的所有子集。策略中的发布者与屏蔽集合按轮次给出,跳过决策可以依赖当时的任务点数。
一个策略的效率定义为:获得的经验总量的期望,除以花费的总时间的期望。这不是“单次随机效率的期望”。令 为所有恰好 轮策略的最大效率,则本题要求