#P18487. 'Ello, and What Are You After, Then?

'Ello, and What Are You After, Then?

'Ello, and What Are You After, Then?

你正在玩 RunEscape。Slayer 是一项反复完成“击杀某类怪物若干只”任务的活动。你想知道怎样最快训练这项技能。

有 nn 位任务发布者(slayer master)。发布者 ii 可以分配 mim_i 种任务。对于其中第 jj 种任务,你知道:

  • fijf_{ij}:该任务的抽取频率权重。
  • tijt_{ij}:完成该任务需要的分钟数。
  • eije_{ij}:执行该任务时每分钟获得的经验值(XP)。完成它共获得 tijeijt_{ij}e_{ij} 点经验。

每完成一个任务,获得 cc 点 slayer points(任务点数)。获得任务后,也可以支付 ss 点任务点数跳过该任务,不完成它、不获得它的经验,也不花费它的执行时间。

反复执行以下一轮操作:

  1. 选择一位任务发布者,记其编号为 ii。
  2. 屏蔽该发布者的至多 bb 种任务,但必须至少留下一种不被屏蔽。设本轮屏蔽的任务下标集合为 BB。抽到第 jj 种任务的概率为
$$\Pr(j)=\begin{cases}\displaystyle\frac{f_{ij}}{\sum_{k\notin B}f_{ik}},&j\notin B,\\0,&j\in B.\end{cases}$$
  1. 发布者按这个概率随机分配一个任务。你可以跳过它并失去 ss 点任务点数,也可以完成它并获得该任务的经验和 cc 点任务点数。
  2. 回到第 1 步,重新选择发布者和本轮屏蔽集合。

你最初有 00 点任务点数,在整个过程中任务点数不能变为负数。因此点数少于 ss 时不能跳过任务。

求在一切选择都最优的情况下,最大可能的长期期望经验获取速率 ee,单位为 XP/分钟。下面的“形式化定义”给出了 ee 的精确含义。

输入格式

第一行三个整数 b,c,sb,c,s,其中 0≤b≤3⋅1040\le b\le3\cdot10^4,1≤c,s≤1041\le c,s\le10^4。

第二行一个整数 nn(1≤n≤1031\le n\le10^3),表示任务发布者数。

随后依次描述每位发布者。先输入一个整数 mim_i(1≤mi≤3⋅1041\le m_i\le3\cdot10^4),再输入 mim_i 行,每行三个整数 fij,tij,eijf_{ij},t_{ij},e_{ij},三者都在 [1,104][1,10^4] 中。

所有发布者的任务种数之和满足 ∑imi≤3⋅104\sum_i m_i\le3\cdot10^4。

输出格式

输出一个浮点数 ee。

当且仅当输出值 aa 与标准答案 zz 满足

∣a−z∣max⁡(1,∣z∣)≤10−6\frac{|a-z|}{\max(1,|z|)}\le10^{-6}

时,认为答案正确。即绝对误差或相对误差不超过 10−610^{-6}。

原样例 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

形式化定义

取一个自然数 qq,考虑恰好执行 qq 轮操作。一个策略是由 qq 个三元组 (ik,Bk,tk)(i_k,B_k,t_k) 组成的序列。第 kk 个三元组描述第 kk 轮的行为:

  • iki_k:这一轮选择的任务发布者。
  • BkB_k:这一轮屏蔽的任务集合,满足上述屏蔽规则。
  • tkt_k:一个函数 N0→2{1,2,…,mik}\mathbb N_0\to 2^{\{1,2,\ldots,m_{i_k}\}}。tk(p)t_k(p) 表示这一轮恰有 pp 点任务点数时,哪些任务被分配后会被跳过。若 p<sp<s,必须有 tk(p)=∅t_k(p)=\varnothing。

这里 N0\mathbb N_0 是非负整数集合,2A2^A 表示集合 AA 的所有子集。策略中的发布者与屏蔽集合按轮次给出,跳过决策可以依赖当时的任务点数。

一个策略的效率定义为:获得的经验总量的期望,除以花费的总时间的期望。这不是“单次随机效率的期望”。令 eqe_q 为所有恰好 qq 轮策略的最大效率,则本题要求

e=lim⁡q→∞eq.e=\lim_{q\to\infty}e_q.