Центр индивидуальной подготовки
школьников и студентов
40-33-54

ЗАДАНИЕ 18 - 103

Исходные данные для Робота записаны в виде электронной таблицы прямоугольной формы. Роботу нужно перейти через поле с запада (левый столбец) на восток (правый столбец). Он может начать переход с любой клетки левого столбца и закончить на любой клетке правого столбца. С каждым шагом Робот переходит в следующий столбец и может за одно перемещение попасть в одну из трех клеток следующего столбца (на клетку прямо и выше или ниже её). Ходы только вверх или вниз (без смены столбца), назад (в предыдущий столбец) и за границы поля запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя с западной границы поля (слева) до восточной границы поля (справа). В ответе укажите два числа: сначала максимальную сумму, затем минимальную.