--->
3 задач
<---
Источники
Хоккей с шайбой — один из самых распространенных в России видов спорта. На днях закончился розыгрыш самого престижного в Европе хоккейного клубного турнира — Кубка Гагарина.
На первом этапе плей-офф борьбу начинает 16 клубов, разбитые по парам. Далее команды, попавшие в одну пару играют между собой серию из семи матчей до четырех побед. Если одна из команд выигрывает четыре матча, то серия прекращается и она признается победителем. Далее остается восемь команд, которые играют второй раунд по тем же правилам, и так далее, вплоть до победителя.
Первые два матча серии проходят на площадке первой команды, следующие два на площадке второй команды, после этого следующие матчи (если они нужны) проходят поочередно сначала на площадке первой команды, потом второй, то есть по схеме 2-2-1-1-1.
Вам дана вероятность победы каждой из команд на каждой из площадок. Вам нужно определить вероятность, с которой серия завершится именно с данным счетом.
Первая строка входного файла содержит вещественных два числа a и b — вероятность победы каждой из команд на площадке первой команды ( 0 ≤ a , b ≤ 1, a + b = 1 ), вторая строка в аналогичном формате вероятность побед из команд на площадке второй команды. Третья строка содержит счет, вероятность которого Вам нужно определить.
Выведите одно число — ответ на задачу. Ответ должен отличаться от правильного не более, чем на 10 - 6 .
0.7 0.3 0.54 0.46 4-0
0.142884
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%
Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .
Игра задаётся перестановкой вершин и происходит следующим образом:
Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 9 + 7 .
В первой строке входного файла дано число N ( 2 ≤ n ≤ 10 5 ) — количество вершин в исходном дереве.
Каждая из последующих N - 1 строк содержит два числа — x i , y i задающих концы соответствующего ребра дерева ( 1 ≤ x i , y i ≤ n ).
Выведите одно число — суммарное количество очков по модулю 10 9 + 7 .
Тесты к данной задаче состоят из 3 групп:
2 1 2
6
3 1 2 2 3
34