Матч 418, Игра в лотерею (TwoLotteryGames)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Возвращаясь домой, вы прочитали объявление: “Выберите m разных чисел между 1 и n включительно. Мы выберем m разных чисел между 1 и n произвольным образом. Если хотя бы k чисел совпадут, то Вы выиграли”.

В задаче требуется вычислить вероятность Вашего выигрыша.

Класс: TwoLotteryGames

Метод: double getHigherChanceGame(int n, int m, int k)

Ограничения: 2 £ n £ 8, 1 £ m £ n – 1, 1 £ k £ m.

Вход. Целые числа n, m и k.

Выход. Вероятность выигрыша игрока.

Пример входа

n	m	k
3	2	1
8	2	1
8	4	2

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

1.0

0.4642857142857143

0.7571428571428571

РЕШЕНИЕ

комбинаторика + вероятность

Рассмотрим случай, когда надо угадать 5 номеров из 39. Очевидно, что вероятность выигрыша составит . Вычислим вероятность того, что угадано будет в точности 4 номера. В этом случае из 5 номеров, задуманных игроком, 4 номера должны находиться среди 5 выпавших ( вариантов), а один номер должен находиться среди 39 – 5 = 34 не выпавших ( вариантов).

В общем случае, для угадывания в точности x номеров, необходимо чтобы эти x номеров находились среди m выпавших, а остальные загаданные m – x номеров игрока находились среди n – m невыпавших. Вероятность угадывания в точности x номеров равна

Для нахождения искомой вероятности следует просуммировать вероятности того, что будет угадано в точности x номеров для x от k до m включительно.

Функция Cnk(k, n) вычисляет значение .

ПРОГРАММА

#include <stdio.h>

int Cnk(int k, int n)

{

long long res = 1;

if (k > n) return 0;

if (k > n - k) k = n - k;

for(int i = 1; i <= k; i++)

res = res * (n - i + 1) / i;

return (int)res;

}

class TwoLotteryGames

{

public:

double getHigherChanceGame(int n, int m, int k)

{

double res = 0;

int x;

for(x = k; x <= m; x++)

res += Cnk(x,m) * Cnk(m-x,n-m);

return res / Cnk(m,n);

}

};