P16046 [ICPC 2022 NAC] Leaderboard Effect

你负责一场编程竞赛，竞赛包含若干道互不相同的题目，并有一个总的时间限制。对于每道题，评委提供了阅读时间、编码时间和解题概率。 在比赛过程中，参赛队伍可以查看显示每支队伍已通过题目的排行榜。看到排行榜会影响队伍的策略！所有队伍在解题时都将遵循以下策略： 1. 选择一道题目来阅读。为了选择读哪道题，他们首先收集所有尚未阅读的题目（如果他们已经读完了所有题目，则剩余时间将什么都不做）。如果这些题目中没有任何一道题已有队伍通过，他们将均匀随机地选择一道题来阅读。否则，他们将按照各题目当前已通过的队伍数量加权随机选择一道题来阅读。例如，如果三题 **A**、**B**、**C** 的已通过数量分别为 3、1、0，那么他们将分别以概率 $\frac{3}{4}$ 选择读 **A**，概率 $\frac{1}{4}$ 选择读 **B**，概率 $\frac{0}{4}$ 选择读 **C**。 2. 在选择了某道题后，他们会先阅读该题。这始终需要该题目给定的阅读时间。阅读完成后，他们会知道自己是否能解出这道题。队伍能以给定的概率解出该题（决定是否可解不花时间）。如果他们不能解出，则返回步骤 1 选择另一道题来阅读。否则，他们会花费给定的时间编码该题（即使比赛剩余时间不足也会编码），然后返回步骤 1 选择下一道题来阅读。一旦队伍完成所选问题的编码，该题即被通过（评测不花时间）；每道题的通过情况会影响排行榜，从而影响其他队伍将尝试的题目。 在所有时间点，排行榜会先更新所有在该时刻发生的通过情况，然后队伍才能看到更新后的排行榜。 设 $f(m, i)$ 为当有 $m$ 支队伍参赛时，预期会通过题目 $i$ 的队伍数量。令 $g(i) = \lim \limits_{m \to \infty}[\frac{f(m,i)}{m}]$，即当队伍数量足够大时，通过题目 $i$ 的队伍数量的期望比例。对于所有题目 $i$，输出 $g(i)$。

输入的第一行包含两个整数 $n$（$1 \le n \le 17$）和 $t$（$1 \le t \le 100$），其中 $n$ 是竞赛中的题目数量，$t$ 是时间限制（单位：分钟）。 接下来的 $n$ 行，每行包含两个整数 $r$ 和 $c$（$1 \le r, c \le t$）以及一个实数 $p$（$0.0 \le p \le 1.0$）。每行描述一道题目，其中 $r$ 是阅读时间（分钟），$c$ 是编码时间（分钟），$p$ 是解出该题的概率。

输出 $n$ 行。每行包含一个实数，表示在队伍数量很大时，预期通过该题目的队伍比例。按输入顺序输出这些比例。答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

翻译由 DeepSeek V3.2 完成