Educational Codeforces Round 13 |
---|
Закончено |
Всем известны правила турнира ситхов. В турнире сражаются n участников. Турнир начинается со случайного выбора двух ситхов, который проводят первый бой. Как только один из них проигрывает, его место занимает другой, случайно выбранный еще не сражавшийся ситх. Надо ли говорить, что каждый бой турнира ситхов заканчивается смертью одного из соперников? Турнир заканчивается, когда в живых остается лишь один ситх.
Джедай Иван случайно оказался в списке участников такого турнира. Однако его владение светлой стороной силы столь велико, что он способен влиять на исход выбора как участников, которые начнут турнир, так и каждого следующего участника поединка. Разумеется, он не станет упускать подвернувшийся шанс улучшить свое положение. Помогите ему рассчитать, насколько велики его шансы победить в турнире.
В первой строке записано единственное число n (1 ≤ n ≤ 18) — количество участников турнира ситхов.
В каждой из следующих n строк записано n вещественных чисел, образующих матрицу pij (0 ≤ pij ≤ 1). Каждый ее элемент pij равен вероятности того, что i-й участник победит j-го в поединке один на один.
Элементы на главной диагонали pii равны нулю. Для любых различных i, j выполняется pij + pji = 1. Все вероятности указаны не более чем с шестью знаками после запятой.
Джедай Иван находится в списке участников под номером 1.
Выведите единственное вещественное число — вероятность, с которой Джедай Иван останется в живых по итогам турнира. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0
0.680000000000000
Название |
---|