n вершин с номерами от 1 до n; рёбра заданы списком links, где [a, b] означает, что вершины a и b соединены.
Жук стартует в вершине 1. Каждую секунду он перебирается в соседнюю вершину, где ещё не бывал, выбирая её случайно и равновероятно среди всех таких соседей. Возвращаться в посещённые вершины он не может. Если непосещённых соседей нет, жук остаётся на месте навсегда.
Найдите вероятность того, что ровно через steps секунд жук окажется в вершине goal. Ответ принимается с точностью до 10⁻⁵.n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=2, goal=5 → 0.25
Из вершины 1 жук с вероятностью 1/2 уходит в 3, а оттуда с вероятностью 1/2 — в 5. Итого 1/4.
n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=7, goal=2 → 0.5
Попав в 2 на первой секунде, жук застревает там: непосещённых соседей нет. Вероятность 1/2.
n=3, links=[[1, 2], [2, 3]], steps=1, goal=2 → 1.0
Через секунду жук наверняка в 2, поэтому ответ 1. Будь steps равно 2, ответ был бы 0: жук успел бы перебраться в 3.
n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=2, goal=5
0.25
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 67 тестов на сервере, включая скрытые.