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

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

Решение

Обьявим двумерный массив x ,  в котором x[time][y]  равно вероятности оказаться в точке с абсциссой $y$ в момент времени $time$. Пусть изначально (в момент времени $t = 0$) Вася находится в точке с абсциссой $y = n$. Тогда x[0][n] = 1 .  Вычислим x[i][j]  – вероятность того что Вася в момент времени $i$ будет находиться в позиции$j$. Для этого Васе следует находиться в момент времени i – 1 либо в позиции j – 1 , либо в позиции j + 1 . Тогда в момент времени $i$ он сможет попасть из них в позицию $j$ с вероятностью 50%. То есть x[i][j] = (x[i – 1][j – 1] + x[i – 1][j + 1]) / 2 .

Ссылки