#include #include #include using db = double; int main() { int32_t n, t; std::cin >> n >> t; std::vector read(n), code(n); std::vector prob(n); for (int32_t i = 0; i < n; ++i) { std::cin >> read[i] >> code[i] >> prob[i]; } // State is the number of problems read. // The distribution of solved problems is purely a function of time // solve_prob[t][x] <- probability x is solved at or before time t. std::vector> solveProb(t + 1, std::vector(n, 0.0)); // team_prob[t][mask] <- probabilty a team is acting at time t and has read the problems in mask. std::vector> teamProb(t + 1, std::vector(1 << n, 0.0)); teamProb[0][0] = 1.0; for (int32_t timeStamp = 0; timeStamp <= t; ++timeStamp) { for (int32_t i = 0; timeStamp > 0 && i < n; ++i) { solveProb[timeStamp][i] += solveProb[timeStamp - 1][i]; } for (int32_t mask = 0; mask < (1 << n); ++mask) { if (teamProb[timeStamp][mask] == 0.0) { continue; } int32_t unread = 0; db denom = 0.0; for (int32_t i = 0; i < n; ++i) { if ((mask & (1 << i)) == 0) { ++unread; denom += solveProb[timeStamp][i]; } } for (int32_t i = 0; i < n; ++i) { if ((mask & (1 << i)) == 0) { db probRead = (denom == 0.0) ? (1.0 / unread) : (solveProb[timeStamp][i] / denom); int32_t readCode = timeStamp + read[i] + code[i]; if (readCode <= t) { db probHere = teamProb[timeStamp][mask] * probRead * prob[i]; teamProb[readCode][mask | (1 << i)] += probHere; solveProb[readCode][i] += probHere; } int32_t readFail = timeStamp + read[i]; if (readFail <= t) { db probHere = teamProb[timeStamp][mask] * probRead * (1.0 - prob[i]); teamProb[readFail][mask | (1 << i)] += probHere; } } } } } std::cout << std::setprecision(20); for (int32_t i = 0; i < n; ++i) { std::cout << solveProb[t][i] << '\n'; } return 0; }