Задача №112581. Футбол
N = 2 K команд играют в турнире по футболу с выбыванием.
В первом раунде играют первая команда со второй, третья с четвёртой, и так далее до последней с предпоследней.
Во втором раунде играют победитель первого матча первого раунда с победителем второго матча второго раунда, победитель третьего матча с победителем четвёртого и так далее до предпоследнего победителя первого матча с победителем последнего матча.
Аналогично играются третий, четвёртый и все раунды до K -ого.
Вам даны вероятности исходов всех возможных встреч в турнире. Определите для каждой команды вероятность того, что она выйдет из турнира - победителем.
Каждый тест состоит из нескольких наборов входных данных (в каждой тесте - не более пяти наборов). Число наборов указано в первой строке входного файла. Каждый набор начинается с числа команд N ( 2 ≤ N ≤ 1024, N - степень двойки). Потом идёт N строк длиной не более 10 - названия команд. Потом идёт матрица NxN , состоящая из целых чисел от 1 до 99 - j -ое число в i -ой строке это вероятность в процентах того, что i -ая команда выиграет j -ую. Вероятности будут дополненные ведущими нулями до двузначных чисел.
2 16 Brazil Chile Nigeria Denmark Holland Yugoslavia Argentina England Italy Norway France Paraguay Germany Mexico Romania Croatia 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 4 Spartak Lokomotiv TCSKA Anzhi 50 42 30 20 58 50 30 10 70 70 50 05 80 90 95 50
Test 1: Brazil 8.54% Chile 1.60% Nigeria 8.06% Denmark 2.79% Holland 4.51% Yugoslavia 7.50% Argentina 8.38% England 1.56% Italy 9.05% Norway 3.23% France 13.72% Paraguay 3.09% Germany 13.79% Mexico 3.11% Romania 5.53% Croatia 5.53% Test 2: Spartak 8.61% Lokomotiv 6.38% TCSKA 3.50% Anzhi 81.51%