10056. Какая вероятность?

n людей подбрасывают некоторую вещь (например, кубик), которая имеет несколько исходов. Если у некоторого игрока случается некоторый наперед установленный выигрышный исход (например, выпала цифра 3), то он объявляется победителем и игра останавливается. Вещь подбрасывается последовательно игроками: сначала первым, потом вторым и так далее. Если у n - ого игрока выигрышный исход не выпал, подбрасывание снова совершается первым игроком, потом вторым и так далее по очереди. Необходимо установить вероятность выигрыша i - го игрока.

Вход. Первая строка содержит количество тестов s (s ≤ 1000). Каждая следующая строка является отдельным тестом и содержит три числа: количество игроков n (n ≤ 1000), вероятность наступления победного события p и номер игрока i (i ≤ 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)ⁿ: для этого необходимо чтобы первый бросок каждого игрока потерпел неудачу (вероятность (1 – p)ⁿ), далее первые 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)ⁿ + p * (1 – p)^i-1 * (1 – p)²ⁿ + … + p * (1 – p)^i-1 * (1 – p)^kn + … =

= p * (1 – p)^i-1 (1 + (1 – p)ⁿ + (1 – p)²ⁿ + .. + (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 < 1e-7) printf("0.0000\n");

else

{

Иначе вычисляем искомую вероятность при помощи приведенной выше формулы. Результат выводим с 4 знаками после десятичной точки.

res = p*pow(1-p,i-1)/(1-pow(1-p,n));

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

}

}