시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 34 | 11 | 9 | 36.000% |
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:
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_{m \rightarrow \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
ICPC > Regionals > North America > North America Championship > North America Championship 2022 F번
Camp > Petrozavodsk Programming Camp > Summer 2022 > Day 1: Welcome Contest K번