题目描述

You are in charge of a programming contest with a number of distinct problems and an overall time limit. The judges provide for each problem a reading time, a coding time, and a solution probability.

During the contest, teams can view a leaderboard that shows the accepted submissions for each team. Seeing the leaderboard can have an effect on teams’ strategies! All teams will follow the following strategy when solving problems in the contest:

1. Choose to read a problem. To choose which problem to read, they first gather all the problems they haven’t yet read (if they have read all problems, they will spend the rest of the contest doing nothing). If none of these problems have any solutions, they will choose to read one uniformly at random. Otherwise, they will choose a problem to read, randomly weighted by the number of solutions that it has. For example, if there are three problems A, B, C with 3, 1, and 0 solutions respectively, they will choose to read problem A with probability $\frac{3}{4}$, problem B with probability $\frac{1}{4}$, and problem C with probability $\frac{0}{4}$.

2. After choosing any given problem, they first read it. This always takes the given reading time for that problem. After they finish reading the problem, they will know if they can solve it or not. The team will be able to solve the problem with the given probability (and this takes no time to decide). If they can’t solve the problem, the team goes back to step 1 and chooses another problem to read. Otherwise, they spend the given time coding the problem (even if there is not enough time left in the contest to finish) before going back to step 1 to choose another problem to read. Once a team finishes coding the chosen problem, the problem is solved (receiving judgement takes no time); each problem solution affects the leaderboard, and therefore the problems other teams will attempt.

At all moments of time, the leaderboard will first update with all the solutions that happened at that time, then teams will see the updated leaderboard.

Let $f(m, i)$ be the expected number of teams that will solve problem $i$ if there are $m$ teams participating in the contest. Let $g(i) = \lim \limits_{m \to \infty}[\frac{f(m,i)}{m}]$, which is the expected proportion of teams that will solve problem $i$ for a large enough number of teams. Output $g(i)$ for all problems $i$ in the set.

输入格式

The first line of input contains two integers $n$ ($1 \le n \le 17$) and $t$ ($1 \le t \le 100$), where $n$ is the number of problems in the contest, and $t$ is the time limit in minutes.

Each of the next $n$ lines contains two integers $r$ and $c$ ($1 \le r, c \le t$) and one real number $p$ ($0.0 \le p \le 1.0$). Each line describes a problem, where $r$ is reading time in minutes, $c$ is coding time in minutes, and $p$ is the probability of solving the problem.

输出格式

Output $n$ lines. Each line contains a single real number, which is the expected proportion of teams that will solve that particular problem, given a large number of teams. Output these proportions for the problems in the same order as the input. The answers are accepted with absolute or relative error at most $10^{-6}$.

4 42
10 10 0.75
10 10 0.75
10 12 1
10 12 1

0.45625
0.45625
0.296875
0.296875

4 42
10 12 0.75
10 12 0.75
10 10 1
10 10 1

0.203125
0.203125
0.683238636363636
0.683238636363636

5 100
40 60 0.6
40 61 1
10 40 0.3
10 40 0.4
10 40 0.5

0.12
0
0.112628571428571
0.159739682539683
0.206444444444444