1580. Простой футбол

Вы смотрите футбольный матч и хотите вычислить вероятность того, что хотя бы одна из команд забьет такое количество голов, которое является простым числом. Игра длится 90 минут. Весь матч разделим на 18 пятиминутных интервалов: от 0 до 5 минуты, от 5 до 10 минуты и так далее. Процентная вероятность забить гол первой командой за любую пятиминутку равна skillOfTeamA, а второй skillOfTeamB. В течение каждой пятиминутки каждая из команд может забить не более одного гола.

Вам необходимо вычислить вероятность того, что хотя бы одна из команд забьет такое количество голов, которое является простым числом.

Вход. Каждая строка содержит два целых числа skillOfTeamA и skillOfTeamB (0 ≤ skillOfTeamA, skillOfTeamB ≤ 100), задающие вероятность в процентах забить гол соответственно первой и второй командой за одну пятиминутку.

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

Пример входа

50 50

100 100

12 89

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

0.5266

0.0000

0.6772

РЕШЕНИЕ

вероятность

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

Обозначим вероятность того, что первая команда забьет количество голов, являющееся простым числом, через pa. Для второй команды эту вероятность обозначим через pb. Поскольку события забивания голов первой и второй командой независимы, то искомая вероятность равна

1 – (1 – pa) * (1 – pb) = pa + pb – pa * pb

Весь матч состоит из 18 пятиминуток, поэтому забито каждой командой может не более 18 голов. Для каждого простого значения p, меньшего 18, следует вычислить вероятность того, что каждая их команд забьет в точности p мячей. Просуммировав эти вероятности для каждой команды, получим значения pa и pb.

k голов команда может забить, забивая в некоторые из k указанных пятиминуток по одному голу, а в остальные пятиминутки не забивая ни одного. Пусть s – вероятность забить гол командой в одну пятиминутку. Тогда вероятность того, что команда забьет мячи в некоторых конкретных k пятиминутках, равна s^k * (1 – s)^{18 – k}. Всего разных k пятиминуток существует . Поэтому вероятность того, что команда забьет ровно k голов, равна. Искомая вероятность pa равна

Аналогично вычисляется вероятность pb.

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

Занесем в массив primes все простые числа, не больше количества пятиминуток в матче.

int primes[7] = {2, 3, 5, 7, 11, 13, 17};

Вычисление искомой вероятности. Функция fact(n) находит факториал числа n.

double getProbability(int skillOfTeamA, int skillOfTeamB)

{

double pa, pb, sa = skillOfTeamA / 100.0, sb = skillOfTeamB / 100.0,

f18 = fact(18);

for(pa = pb = i = 0; i < 7; i++)

{

pa += f18 / fact(primes[i]) / fact(18 - primes[i]) * pow(sa, primes[i]) *

pow(1 - sa, 18 - primes[i]);

pb += f18 / fact(primes[i]) / fact(18 - primes[i]) *

pow(1.0 * sb, primes[i]) * pow(1.0 - sb, 18 - primes[i]);

}

return pa + pb - pa * pb;

}

Основная часть программы.

while(scanf("%d %d",&skillOfTeamA,&skillOfTeamB) == 2)

{

res = getProbability(skillOfTeamA, skillOfTeamB);

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

}