SP13801 DEXTER - Dexter Rank

Dexter 刚参加了一场编程竞赛，目前正在等待评审结果。每次等待都让他非常无聊，因此他希望根据当前的排行榜情况以及每道题出错的可能性，来预估自己的期望排名。具体来说，这场比赛有 $M$ 道题目，有 $N$ 名选手参赛。Dexter 已经知道，第 $i$ 位选手完成第 $j$ 道题所用的罚时为 $penalty[i][j]$。同时，他也知道第 $j$ 道题在通过系统测试时的成功概率为 $prob[j]$（这同样适用于 Dexter 自己）。每个选手对每道题的解决情况是独立的。现在，Dexter 想要知道在系统测试结束后，他的期望排名是多少。 需要注意的是，选手是根据正确解决题目的数量进行排名的；如果数量相同，则以所有正确解题的罚时多少决定排名；如果罚时也相同，则并列排名。 举个例子：假设系统测试后的排行榜如下： - 选手 1：300 -1 -1，得分：1，罚时：300 - 选手 2：100 -1 200，得分：2，罚时：300 - 选手 3：-1 300 -1，得分：1，罚时：300 - 选手 4：-1 -1 400，得分：1，罚时：400 对应的排名将是：2 1 2 4。

第一行输入一个整数 $T$，表示测试用例的数量。 对于每个测试用例： - 第一行输入两个空格分隔的整数 $N$ 和 $M$。 - 接下来的 $N$ 行中，每行包含 $M$ 个整数，第 $i$ 行的第 $j$ 个整数表示 $penalty[i][j]$，即第 $i$ 位选手对第 $j$ 道题的罚时，如果未提交则为 -1。 - 第 $M + 1$ 行中包含 $M$ 个空格分隔的整数，每个整数表示相应题目的通过系统测试的概率 $prob[i]$。 Dexter 是列表中的第一个选手。

输出 Dexter 在系统测试后的期望排名，要求保留到四位小数。

- $1 \le T \le 16$ - $2 \le N \le 256$ - $1 \le M \le 12$ - $1 \le penalty[i][j] \le 1000000$ 或 $penalty[i][j] = -1$ - $0 \le prob[j] \le 100$ ## 示例 ### 输入 ``` 3 2 1 100 150 50 2 2 -1 -1 10 -1 0 100 3 2 100 200 -1 199 99 -1 50 50 ``` ### 输出 ``` 1.2500 1.0000 1.6250 ``` ### 解释 - 对于第一个测试用例，如果 Dexter 的解决方案通过或者第二位选手的解决方案不通过，那么他的排名就是第一，这种情况发生的概率是 0.75；否则他的排名是第二位。因此，答案为 $1 \times 0.75 + 2 \times 0.25 = 1.2500$。 - 对于第二个测试用例，所有选手在任何情况下都没有解出题目，因此皆为第一，所以答案是 1.0000。 **本翻译由 AI 自动生成**