| MemSQL Start[c]UP 3.0 - Round 1 |
|---|
| Закончено |
Приближается ежегодное школьное соревнование по спортболу, по причинам копирайта назовем его «Сумасшествие третьего месяца». Всего будут участвовать 2N команд, пронумерованных от 1 до 2N. В турнире будет N раундов, в каждом раунде половина команд будет выбывать. Первый раунд будет состоять из 2N - 1 игр, пронумерованных с 1. В игре номер i команда 2·i - 1 сыграет с командой 2·i. Проигравший выбывает, а победитель проходит в следующий раунд (ничьих не бывает). В каждом последующем раунде вдвое меньше игр, чем в предыдущем, и в игре номер i играет победитель игры номер 2·i - 1 предыдущего раунда против победителя игры номер 2·i предыдущего раунда.
Каждый год в офисе проходит соревнование по построению лучшей турнирной сетки. Турнирная сетка — это набор предсказаний победителя в каждой игре. Для игр первого раунда можно любую из двух команд выбрать победителем, а для игр из более поздних раундов необходимо, чтобы предсказанный победитель был также предсказанным победителем в предыдущем раунде. Заметьте, что турнирная сетка строится перед тем, как начнутся игры. Правильные предсказания в первом раунде дают составителю 1 очко, а правильные предсказания в каждом последующем раунде дают в два раза больше очков, чем в предыдущем. Таким образом, правильное предсказание в финале дает 2N - 1 очков.
Для каждой пары команд среди участников вы оценили вероятность победы каждой игры, если эти команды сыграют между собой. Теперь вы хотите построить турнирную сетку с максимальным математическим ожиданием суммарного количества очков.
Первая строка содержит одно целое число N (2 ≤ N ≤ 6).
Далее следуют 2N строк, каждая содержит 2N целых чисел. j-е число в i-й строке равно вероятности того, что команда i выиграет команду j, кроме случая i = j, в котором это значение будет равно 0. Гарантируется, что сумма i-го числа в j-й строке и j-го числа в i-й строке в точности равна 100.
Выведите максимально возможное математическое ожидание суммарного числа очков среди всех возможных турнирных сеток. Ваш ответ должен быть правильным с абсолютной или относительной точностью 10 - 9.
Формально, пусть ваш ответ равен a, а ответ жюри равен b. Ваш ответ будет считаться правильным, если 
.
2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0
1.75
3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0
12
2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0
3.141592
В первом примере вы должны выбрать команды 1 и 4 как победителей в раунде 1, и команду 1 как победителя в раунде 2. Обратите внимание, победитель в раунде 2 должен быть победителем в раунде 1.
