Задача K. Bad game ≡

Условие

В ДВФУ при оценке выполнения студентами заданий используется система AWorks, которая снижает баллы за не вовремя сданное задание. Однажды преподаватель решил больше не мучить студентов и разработал игру, в которой нужно уничтожать монстров, давая им задания.

Всего в игре M монстров, им даётся N заданий. Каждый монстр характеризуется успешностью p_i — это вероятность, с которой он сдаст задание вовремя. За вовремя сданное задание монстр получает 1 балл, за не вовремя сданное задание — 0.5 балла. Монстру необходимо заработать не менее A баллов.

Какое количество монстров заработает не менее A баллов и не будут уничтоженными? Найдите распределение вероятностей.

Монстры действуют независимо друг от друга, и сдача одного задания не зависит от сдачи другого задания.

Формат входного файла

Входной файл содержит целые числа N A M, за которыми следуют M вещественных чисел p_i.

Формат выходного файла

Требуется вывести в выходной файл M + 1 пар чисел k c_k, где k = 0, 1, ..., M, а c_k — вероятность того, что ровно k монстров не будут уничтожены, с точностью до 5-ти знаков после запятой.

Ограничения

1 ≤ A ≤ N ≤ 10

1 ≤ M ≤ 10

0.01 ≤ p_i ≤ 1

Примеры тестов

4 3 2
0.5 0.3

0 0.20366
1 0.55689
2 0.23946

3 1 1
0.1

0 0.00000
1 1.00000

Разбор

Если монстр выполнил k заданий, то он получит 0.5(N − k) + k баллов, поэтому, чтобы закрыть сессию, нужно, чтобы 0.5(N − k) + k ≥ A, или k ≥ 2A − N.

Сначала найдём для каждого монстра индивидуальную вероятность закрытия сессии, которую обозначим P_i. Вероятность того, что монстр сдаст ровно k заданий, равна CkNpki(1 − p_i)^N − k. Поэтому вероятность P_i того, что i-й монстр закроет сессию, равна сумме этого выражения по k от s до N, где s = max{2A − N, 0}.

Далее, зная индивидуальные вероятности, найдём общее распределение вероятностей для всех монстров. Для этого рассмотрим элементарные события — переберём все возможные последовательности из M нулей и единиц. Ноль означает, что i-й монстр не закрыл сессию, а единица означает, что закрыл.

Для каждого элементарного события вычислим его вероятность, которая равна произведению чисел P_i в случае закрытия сессии и 1 − P_i в случае не закрытия. Пусть k — количество закрывших сессию. Тогда прибавим вычисленное произведение к элементу массива c_k. В итоге мы переберём все возможные исходы сдачи сессии для всех монстров и сгруппируем эти исходы по количеству закрывших сессию монстров, вычислив вероятность для каждой группы.