4078. Извлечение мраморных камешков

Большая коробка содержит мраморные камешки одного или нескольких цветов. Известно количество камешков каждого цвета. Вы произвольным образом извлекаете n камешков из коробки, не возвращая их обратно. Найти вероятность того, что все вытянутые камешки будут иметь одинаковый цвет.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество цветов col (1 ≤ col ≤ 50) и значение n. Во второй строке задаются col целых чисел c₁, c₂, .., c_col, где c_i (1 ≤ c_i ≤ 50) – количество мраморных камешков цвета i. Известно, что 1 ≤ n ≤ c₁ + c₂ + .. + c_col.

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

Пример входа	Пример выхода
1 8 13 3 2 5 6 7 5 4 12 2 34 13 17	1.0000 0.3007 0.0350

РЕШЕНИЕ

теория вероятности

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

Вычислим общее количество камешек в коробке. Оно равно total = c₁ + c₂ + .. + c_col. Пусть первым мы вынимаем из коробки камешек цвета i. Вероятность этого события равна c_i / total. Пусть второй извлекаемый из коробки камешек также имеет цвет i. Вероятность этого события равна (c_i – 1) / (total – 1). Вероятность p_i того, что все вынутые n камешков имеют цвет i, равна

Отметим, что если n > c_i, то указанная вероятность равна нулю. Остается просуммировать вероятности p₁ + p₂ + … + p_col.

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

Читаем входные данные.

while(scanf("%d %d",&col,&n) == 2)

{

Вычисляем общее количество камешков в переменной total.

total = 0

for(i = 1; i <= col; i++)

{

scanf("%d",&colors[i]);

total += colors[i];

}

В переменной res находим искомую вероятность.

res = 0;

Перебираем цвета. Для каждого цвета i вычисляем вероятность p вынуть из коробки все n камешков цвета i.

for(i = 1; i <= col; i++)

{

Если c_i < n, то невозможно извлечь n камней цвета i. Вероятность p в таком случае равна 0.

if (colors[i] < n) continue;

Вычисляем вероятность p.

p = 1;

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

p *= 1.0 * (colors[i] - j) / (total - j);

Прибавляем вероятность p к общему результату.

res += p;

}

Выводим ответ.

printf("%.4lf\n",res);

}