1571. Какая вероятность?
Вероятность
всегда была неотъемлемой частью компьютерных алгоритмов. Там, где
детерминированные алгоритмы не могли решить задачу за разумное время,
использовались вероятностные алгоритмы. В этой задаче Вам следует определить
вероятность выигрыша определенного игрока.
Рассмотрим игру,
в которой бросается некоторая вещь (например, кубик), которая имеет несколько
исходов. Если у некоторого игрока случается некоторый наперед установленный
выигрышный исход (например, выпала цифра 3, или сверху выпал зеленый цвет, или
еще что-нибудь), то он объявляется победителем и игра останавливается. Всего
имеется n игроков. Вещь
подбрасывается игроками последовательно: сначала первым, потом вторым и так
далее. Если у n - го игрока
выигрышный исход не выпал, то подбрасывание снова совершается первым игроком,
потом вторым и так далее по очереди. Необходимо установить вероятность выигрыша
i - го игрока.
Вход. Первая строка содержит количество тестов t (t ≤ 1000).
Каждая следующая строка является отдельным тестом и содержит три числа:
количество игроков n (n ≤ 1000), действительное число p, равное вероятности наступления
победного события и номер игрока i (i ≤ n), вероятность выигрыша которого следует подсчитать (игроки
пронумерованы числами от 1 до n). Входные
данные корректны.
Выход. Для каждого
теста в отдельной строке вывести вероятность выигрыша i-го игрока с четырьмя десятичными знаками.
|
Пример
входа |
Пример
выхода |
|
2 2 0.166666 1 2 0.166666 2 |
0.5455 0.4545 |
РЕШЕНИЕ
вероятность
Анализ алгоритма
Вероятность
того, что i - ый игрок на первом же
своем броске выиграет, равна p * (1 –
p)i-1.
Вероятность того, что i - ый игрок
выиграет при втором своем броске, равна p
* (1 – p)i-1 * (1 – p)n: для этого
необходимо чтобы первый бросок каждого игрока потерпел неудачу (вероятность (1
– p)n), далее первые i
– 1 игроков не получили выигрышный исход (вероятность (1 – p)i-1),
и наконец, i - ый игрок выиграл,
совершив свой бросок с вероятностью p.
Соответственно, i - ый игрок выиграет на k - ом своем броске с вероятностью
p * (1 – p)i-1 * (1 – p)
kn
Просуммируем
вероятности выигрыша i - ого игрока.
Искомая вероятность его выигрыша равна
p * (1 – p)i-1
+
p * (1 – p)i-1
* (1 – p)n +
p * (1 – p)i-1
* (1 – p)2n + … +
p * (1 – p)i-1
* (1 – p)kn + … =
= p *
(1 – p)i-1 (1 + (1 – p)n + (1 – p)2n + .. + (1 – p)kn + …)
и образует
бесконечную геометрическую прогрессию, сумма которой равна
p * (1 – p)i-1 
= 
Отдельно следует
обработать случай, когда p = 0. В
таком случае ответом будет 0.
Реализация алгоритма
Читаем входные
данные.
scanf("%d",&s);
while(s--)
{
scanf("%d %lf
%d",&n,&p,&i);
Если вероятность p равна 0, то выводим 0.
if (p == 0)
printf("0\n");
else
{
Иначе вычисляем искомую вероятность
при помощи приведенной выше формулы. Результат выводим с 4 знаками после
десятичной точки.
res = p * pow(1-p,i-1) / (1 - pow(1-p,n));
printf("%.4lf\n",res);
}
}