Олимпиадный тренинг

Задача . E. Рыбы


Задача

Темы: битмаски дп Теория вероятностей *1900

В озере живет n рыб, пронумерованных от 1 до n. Каждый день ровно одна пара рыб встречается друг с другом, причем вероятности встречи каждой пары равны между собой. Если две рыбы с номерами i и j встретились, то первая съест вторую с вероятностью aij, а вторая первую –– с вероятностью aji = 1 - aij. Этот процесс продолжается, пока в озере остается хотя бы две рыбы. Для каждой рыбы посчитайте вероятность того, что она останется последней в озере.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 18) — число рыб в озере. Далее следует n строк по n вещественных чисел — матрица a. aij (0 ≤ aij ≤ 1) — вероятность того, что рыба с номером i съест рыбу с номером j. Гарантируется, что на главной диагонали матрицы стоят нули, а для всех остальных элементов выполняется: aij = 1 - aji. Все вещественные числа даны не более чем с 6 знаками после десятичной точки.

Выходные данные

Выведите n вещественных чисел, разделенных пробелами, с точностью не менее 6 знаков после точки. Число с номером i должно быть равно вероятности того, что рыба с номером i останется последней в озере.


Примеры
№Входные данныеВыходные данные
1 2
0 0.5
0.5 0 
0.500000 0.500000
2 5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0 
1.000000 0.000000 0.000000 0.000000 0.000000

time 3000 ms
memory 128 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет