Вы решили принять участие в кроссе по лесу, через который проложена замысловатая сеть дорожек, усыпанных крупными валунами. Вы начинаете бег со старта и можете двигаться к финишу по любым дорожкам. Однако камни мешают бегу, поэтому вы выбираете те дорожки, на которых меньше всего валунов.
Какое наименьшее количество валунов вы можете встретить на пути от старта к финишу?
Ответ, как обычно, вы узнаете ниже.
К этой задаче можно применить теорию графов и провести несложные вычисления. Но можно попытаться найти оптимальный маршрут методом перебора. А лучше всего пойти немного другим путём – начать движение от финиша к старту, на каждом перекрёстке выбирая дорожку с наименьшим числом валунов. Стоя у финиша, мы оказываемся у дорожек с четырьмя и семью валунами – мы выбираем дорожку с четырьмя валунами. На следующем перекрёстке мы оказываемся перед дорожками с шестью, тремя и одним валуном – мы бежим по последней. И так далее до старта. Получится такой маршрут:
Нетрудно посчитать, что на этом маршруте вы встретите 11 валунов. Других маршрутов с меньшим или равным количеством валунов здесь нет. А наибольшее количество валунов, которые можно встретить – 21, этот маршрут вы тоже найдёте без труда.