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

Вероятность часто является неотъемлемой частью компьютерных алгоритмов. Когда детерминированные алгоритмы не способны решить задачу за разумное время, на помощь приходят вероятностные алгоритмы. Однако в данной задаче от вас не требуется разрабатывать вероятностный алгоритм — необходимо лишь вычислить вероятность того, что конкретный игрок выиграет игру.

В игре участвуют n игроков, которые по очереди бросают объект, похожий на игральную кость (при этом количество граней не обязательно равно шести). Ходы выполняются по порядку: сначала первый игрок, затем второй и так далее до n-го. Если в некотором раунде ни один из игроков не выигрывает, игра продолжается заново, начиная с первого игрока.

Игрок выигрывает, если во время его хода происходит определённое событие (например, выпадает число 3, зелёная грань и тому подобное), после чего игра немедленно завершается. Вероятность наступления этого выигрышного события при одном броске равна p.

Определите вероятность того, что победит игрок с номером i.

Вход. Первая строка содержит количество тестов t (t ≤ 1000). Каждая из следующих t строк содержит три значения: количество игроков n (n ≤ 1000), вещественное число  p (0 ≤ p ≤ 1) – вероятность выигрышного события при одном броске и номер игрока i (1 ≤ i ≤ n), для которого следует вычислить вероятность выигрыша.

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

Пример входа	Пример выхода
2 2 0.166666 1 2 0.166666 2	0.5455 0.4545

РЕШЕНИЕ

вероятность

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

Рассмотрим игру с точки зрения теории вероятности:

· Каждый бросок независим от остальных;

· Вероятность выигрыша в одном броске равна p;

· Вероятность неудачи в одном броске равна 1 – p;

· Игроки ходят по кругу: 1, 2, …, n, 1, 2, … ;

· Игра заканчивается сразу, как только кто-то выигрывает.

Нас интересует вероятность того, что выиграет -й игрок.

Факт выигрыша i-го игрока означает, что:

· до его победного броска никто не выиграл;

· на его ходе выигрышное событие произошло.

При этом i-й игрок может выиграть:

· на своём первом броске;

· на своём втором броске;

· на своём третьем броске;

· и так далее.

Итоговая вероятность равна сумме вероятностей всех этих случаев.

Чтобы i-ый игрок выиграл на своём первом ходе, должны выполниться два условия:

· Первые i – 1 игроков не выиграли. Вероятность события равна (1 – p)^{i – 1}

· i-ый игрок выиграл. Вероятность события равна p.

Так как события независимы, то вероятность для i-го игрока выиграть на своём первом ходе равна

p ∙ (1 – p)^{i – 1}

-й игрок выиграет на своём втором ходе, если:

· Все n игроков сделали по одному броску и проиграли:

· Первые i – 1 игроков во втором круге снова проиграли. Вероятность события равна (1 – p)^{i – 1}.

· i-ый игрок выиграл. Вероятность события равна p.

Вероятность для -го игрока выиграть на своём втором ходе равна

p ∙ (1 – p)^{i – 1} ∙ (1 – p)ⁿ

Аналогично рассуждая, мы получим что вероятность для i-го игрока выиграть на своём k-ом ходе равна

p ∙ (1 – p)^{i – 1} ∙ (1 – p)^{n(k – 1)}

Теперь остается просуммировать полученные вероятности. Общая вероятность выигрыша i-го игрока равна

p ∙ (1 – p)^i-1 (1 + (1 – p)ⁿ + (1 – p)²ⁿ + .. + (1 – p)^kn + …)

В скобках находится бесконечная геометрическая прогрессия с первым членом 1 и знаменателем (1 – p)ⁿ. Вероятность выигрыша равна

p ∙ (1 – p)^i-1 =

Отдельно следует отметить, что при p = 0 ответ равен 0.

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

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

scanf("%d",&t);

while(t--)

{

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);

}

}