1578. Заданная вероятность

n друзей собрались за покупками в супермаркет. Вероятность купить что-либо составляет p₁, p₂, …, p_n соответственно для каждого друга. После посещения магазина оказалось, что в точности r друзей совершили покупки (остальные ничего не купили). Определить вероятность покупательской способности каждого друга при выполнении этого условия.

Вход. Содержит не более 50 тестов. Первая строка каждого теста содержит два числа n () и r (). Каждая из следующих n строк содержит вероятность покупки i - го друга p_i (). Все вероятности содержат как минимум два знака после десятичной точки. Последний тест содержит n = r = 0 и не обрабатывается.

Выход. Для каждого теста вывести его номер, а также n строк. i - ая строка должна содержать вероятность покупательной способности i - го друга при условии, что в точности r друзей совершили покупки. Вероятности следует выводить с 6 знаками после десятичной точки.

Пример входа

3 2

0.10

0.20

0.30

5 1

0.10

0.10

0.10

0.10

0.10

0 0

Пример выхода

Case 1:

0.413043

0.739130

0.847826

Case 2:

0.200000

0.200000

0.200000

0.200000

0.200000

РЕШЕНИЕ

вероятность + перебор

Анализ алгоритма

Вычислим вероятность P того, что в точности r друзей совершат покупки. Для этого переберем все подмножества из r друзей (их не более ). Одновременно для каждого друга вычисляем вероятность prob_i того, что он совершит покупку при условии, что в точности r друзей купили что-нибудь. Таким образом, вероятность покупательской способности i - ого друга при условии совершении покупок в точности r друзьями, составит prob_i / P.

Пример

Рассмотрим первый тест. Двум купившим друзьям из трех будут соответствовать последовательности 011, 101, 110. Требуемые вычисления приведены в таблице:

последоват.	подмножество	вероятность	prob[1]	prob[2]	prob[3]
011	{2, 3}	0.9 * 0.2 * 0.3 = 0.054	-	0.054	0.054
101	{1, 3}	0.1 * 0.8 * 0.3 = 0.024	0.024	-	0.024
110	{1, 2}	0.1 * 0.2 * 0.7 = 0.014	0.014	0.014	-
сумма вероятностей P		0.092	0.038	0.068	0.078
prob[i] / P			0.413043	0.739130	0.847826

Реализация алгоритма

Исходные вероятности покупки друзей p_i храним в массиве p. В переменной all вычисляем вероятность того, что в точности r друзей из n совершат покупки. Вероятность покупки каждого друга при условии, что в точности r друзей купили что-нибудь, будем хранить в ячейках массива prob.

double p[21], prob[21], all;

int m[21];

Функция generate генерирует последовательности длины n, состоящие из n – r нулей и r единиц. Каждой такой последовательности соответствует подмножество из r друзей. Для каждого подмножества друзей вычисляем вероятность их покупок и добавляем к all. Если в это подмножество входит i - ый друг, то вероятность прибавим и к prob[i].

void generate(int pos, int r)

{

double p1;

int i;

if ((pos + r > n) || (r < 0)) return;

if (!r && (pos == n))

{

for(p1 = 1.0, i = 0; i < n; i++)

if (m[i]) p1 *= p[i]; else p1 *= (1 - p[i]);

all += p1;

for(i = 0; i < n; i++)

if (m[i]) prob[i] += p1;

return;

}

generate(pos+1,r);

m[pos] = 1;

generate(pos+1,r-1);

m[pos] = 0;

}

Основной цикл программы. Читаем входные данные. Заданные вероятности сохраняем в массиве p.

while(scanf("%d %d",&n,&r), n + r)

{

for(all = i = 0; i < n; i++) scanf("%lf",&p[i]);

memset(m,0,sizeof(m)); memset(prob,0,sizeof(prob));

Генерируем последовательности длины n из r единиц.

generate(0,r); // pos, r

Для каждого друга выводим искомую вероятность.

printf("Case %d:\n",cs++);

for(i = 0; i < n; i++)

printf("%.6lf\n",prob[i]/all);

}