Майор Пронин и шпион

[fortpost]

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

[Александр Кремень]

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

[moonlight]

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

[fortpost]

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

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

[moonlight]

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

[fortpost]

moonlight - 

[☭-Изделие 20Д]

http://nazva.net/forum/in....msg196967.html#msg196967

[fortpost]

http://nazva.net/forum/in....msg196967.html#msg196967

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