Форум умных людей

Страна Фарра расположена на 1 000 000 000 островов. Между некоторыми островами каждый день курсируют пароходы. Маршруты пароходов устроены так, что с каждого острова можно попасть на любой другой (возможно, за несколько дней). Шпион и майор Пронин могут совершать не более одного рейса в день на пароходе и не имеют никакой другой возможности попасть с острова на остров. Шпион не ездит на пароходе 13 числа каждого месяца, майор Пронин не суеверен и всегда знает, где находится шпион. Как майор сможет поймать шпиона (т.е. оказаться с ним на одном острове)?

За один день все острова обойти невозможно.Надо что-то рассчитать...

В худшем случае погоня будет длится более 40 000 000 лет.

Майор Пронин бессмертен! 8) :laugh:
А как все же ему организовать погоню?

Для любой пары островов можно определить кратчайший маршрут между ними (в смысле минимального числа переездов которые нужно сделать чтобы попасть с одного острова на другой). Таких маршрутов может быть более одного - тогда выбирается один из них. Всякий раз в зависимости от того на каких островах в данный момент находятся Пронин и шпион, Пронин вычисляет такой маршрут и переезжает на первый остров. В этом случае расстояние между ним и шпионом увеличиваться не будет при любой стратегии шпиона, а 13 числа каждого месяца оно будет сокращаться минимум на один переезд.

moonlight -  :good2:

http://nazva.net/forum/index.php/topic,7358.msg196967.html#msg196967

Та ведь это ж совсем две большие разницы!