P9144 [THUPC 2023 初赛] 最后的活动

各位亲爱的《La Lumière: Scarlet Intense Flame》玩家： 感谢您一直给予《La Lumière: Scarlet Intense Flame》的支持与厚爱。我们非常遗憾地宣布，《La Lumière: Scarlet Intense Flame》将于 2023 年 3 月 5 日 16:00 停止运营服务。 停止运营相关时间表如下： ……

元老级二次元手游《La Lumière: Scarlet Intense Flame》将于今年 3 月停止运营服务。作为这款游戏的忠实玩家，小 S 希望能在游戏的最后一次活动中刷到一个特殊的分数，以此为近十年来与这款游戏共度的难忘时光画上一个圆满的句号。 《La Lumière: Scarlet Intense Flame》中的每种活动都有其独特的规则，而最后一次活动是 Chase Festival。在 Chase Festival 中，玩家需要多次攻略每次随机生成的多层迷宫，每次退出迷宫时根据在迷宫中各层击杀怪物的评价独立结算本次随机迷宫的分数。每次挑战迷宫时的流程简化如下： 1. 选择挑战的随机迷宫的难度。小 S 是这款游戏的资深玩家，因此在本题中假定小 S 总是挑战最高难度的迷宫。最高难度的迷宫最深为 $N$ 层。确定难度后，从随机生成的迷宫的第 1 层开始挑战。 2. 进行第 $i$ 层的挑战。挑战第 $i$ 层时，小 S 有可能挑战失败，挑战成功并获得普通评价，或者挑战成功并获得高评价。如果小 S 选择保守的挑战策略，则有 $p_{i,0}$ 的概率挑战失败，有 $p_{i,1}$ 的概率挑战成功并获得普通评价，有 $p_{i,2}$ 的概率挑战成功并获得高评价；如果小 S 选择激进的挑战策略，则有 $q_{i,0}$ 的概率挑战失败，有 $q_{i,1}$ 的概率挑战成功并获得普通评价，有 $q_{i, 2}$ 的概率挑战成功并获得高评价。 - 获得普通评价时，在当前层获得 $s_{i,1}$ 的分数；获得高评价时，在当前层获得 $s_{i,2}$ 的分数。这部分获得的分数**不会直接加算**到玩家的总分数中，而是**在退出迷宫时结算**。如果挑战成功，且当前不是最后一层（$i

输入的第一行包含三个整数 $N, M, c'$，其中 $N$ 和 $M$ 的含义与题面相同，$c'=100c$。保证 $1\le N\le 6$，$1\le M\le 10000$，$0\le c'\le 100$。 接下来 $N$ 行，每行输入八个整数 $s_{i,1},s_{i,2},u_{i,0},u_{i,1},u_{i,2}, v_{i,0}, v_{i,1}, v_{i,2}$，其中 $s_{i,1}$ 与 $s_{i,2}$ 分别表示挑战时普通评价和高评价对应的分数；$u_{i,j}$ 和 $v_{i,j}$ 分别表示使用保守的挑战策略及激进的挑战策略时，对应结果的概率权重：$p_{i,j}=\dfrac{u_{i,j}}{u_{i,0}+u_{i,1}+u_{i,2}}$，$q_{i,j}=\dfrac{v_{i,j}}{v_{i,0}+v_{i,1}+v_{i,2}}$。保证 $1\le s_{i, 1} \le s_{i, 2}\le 10000$，$0\le u_{i,j}, v_{i,j}\le 10000$ 且 $u_{i,1}+u_{i,2}\ge 1$，$v_{i,1}+v_{i,2}\ge 1$。

输出一行 $M$ 个实数，其中第 $i$ （$1\le i\le M$）个实数表示当距离目标分数恰好还剩 $i$ 分时，在最优策略下能够恰好获得 $i$ 分的最大概率。 当你输出中的每个实数与相应标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

#### 子任务 对于 $100\%$ 的数据，保证 $1\le N\le 6$，$1\le M\le 10000$，$0\le c'\le 100$，$1\le s_{i,1}\le s_{i, 2}\le 10000$，$0\le u_{i, 0}, u_{i, 1}, u_{i, 2}, v_{i, 0}, v_{i, 1}, v_{i, 2}\le 10000$，$u_{i,1}+u_{i,2}\ge 1$，$v_{i,1}+v_{i,2}\ge 1$。 #### 提示 《La Lumière: Scarlet Intense Flame 2》将于 2023 年春暖花开的时节与大家相见！ #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。 题解等资源可在 查看。