e-olymp 7261. Трудный путь

Задача

Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!

Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.

Входные данные

В одной строке содержатся два целых числа $n$ и $m$ [latex](0 \le n , m \le 1000)[/latex].

Выходные данные

Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.

Тесты

Входные данные Выходные данные
1 1 0.500000000
10 20 0.000000000
1000 100 0.000169397
16 2 0.174560547
90 44 0.000001273

Код программы

Решение

Закодируем путь Васи последовательностью из 0 и 1. Пусть 1 соответствует движению вправо, а 0 влево. Пусть из $n$ шагов, которые совершил Вася, $k$ шагов он сделал вправо. Тогда $n-k$ шагов он сделал влево.Нас интересует вероятность того, что Вася переместился в одну из сторон (например вправо) на $m$ кварталов. Тогда должно выполняться: $m+n-k=k$откуда $k=\frac{m+n}{2}$.Количество последовательностей длины $n$ с $k$ единицами равно $C_n^k$. Поскольку Вася совершил $n$ перемещений, то у него имеется $2^n$ вариантов выбора различных путей. Следовательно вероятность того что Вася пройдет вправо m кварталов, равна $\frac{C_n^k}{2^n}$, где $k=\frac{m+n}{2}$. Отметим, что искомая вероятность равна 0, если $m+n$ нечетно. В этом случае Вася просто не сможет попасть домой, то есть $m+n=2k$ четно.

Ссылки

e-olymp 1317. Дни рождения

Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

Входные данные

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

Выходные данные

Для каждого значения [latex]n[/latex] в отдельной строке вывести вероятность того, что хотя бы у двух из [latex]n[/latex] людей дни рождения (число и месяц) совпадают. Искомую вероятность выводить в процентах и округлять до [latex]8[/latex] знаков после запятой как указано в примере.

Тесты

Входные данные Выходные данные
[latex]12[/latex] [latex]16.70247888\%[/latex]
[latex]28[/latex] [latex]65.44614723\%[/latex]
[latex]399[/latex] [latex]100.00000000\%[/latex]

Код программы

Решение задачи

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.