Графы, поиск пути и выигрышные стратегии

Для ориентированного графа без циклов количество путей в вершину равно сумме количеств путей во все вершины, из которых в неё ведёт дуга. Стартовая вершина помечается единицей. Вершины обрабатываются в таком порядке, чтобы к моменту подсчёта все предшественники уже были посчитаны.

Условие: на рисунке схема дорог с односторонним движением: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Д, Г→Е, Д→Е. Сколько существует различных путей из города А в город Е, проходящих через город Г? Решение. 1) Считаем пути из А в Г: N(А) = 1, N(Б) = 1, N(В) = 1, N(Г) = N(Б) + N(В) = 2. 2) Считаем пути из Г в Е: из Г можно сразу в Е (1 путь) либо Г→Д→Е (1 путь), итого 2. 3) Пути через Г: 2 · 2 = 4. Для справки: всего путей из А в Е равно 5 (по таблице выше), значит ровно один путь идёт мимо Г — это А→В→Д→Е. В бланк: 4

Условие: два игрока, Петя и Ваня, играют в игру. Перед ними куча из S камней. Игроки ходят по очереди, Петя ходит первым. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда количество камней становится не менее 40. Выигрывает игрок, сделавший последний ход. Найдите минимальное значение S, при котором Петя выигрывает своим первым ходом. Решение. Петя выигрывает первым ходом, если хотя бы один из его ходов сразу даёт не менее 40 камней: S + 1 ≥ 40 (то есть S ≥ 39) или 2S ≥ 40 (то есть S ≥ 20). Минимальное подходящее S равно 20 — удвоение даёт ровно 40. Проверка на Python: print(min(s for s in range(1, 40) if s + 1 >= 40 or 2*s >= 40)) В бланк: 20

В играх формулировка «игра завершается, когда камней становится не менее 40» означает ≥ 40, а не > 40: удвоение 20 до ровно 40 уже выигрывает. В графах формулировка «проходящих через Г» требует умножения двух чисел, а «минуя Г» — удаления вершины Г и пересчёта. Ещё одна частая ошибка — считать маршруты в неориентированном графе как в ориентированном: если направление не указано, путей будет больше, и понадобится явный перебор без повторного посещения вершин.