Решение задач «Задание 18 из ЕГЭ»,
Информатика в Санкт-Петербурге

121) (А. Богданов) Исходные данные для Робота записаны в виде электронной таблицы прямоуголь-ной формы. Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки первой строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в следующую строку и может за одно перемещение попасть в одну из трех клеток следующей строки (на клетку прямо вниз или на одну из клеток слева/справа от неё). Ходы только влево или вправо (без смены строки), назад (в предыдущую строку),за грани-цы поля и в цветные клетки запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите максимальную и мини-мальную денежную сумму, которую может собрать Робот, пройдя с северной границы поля (свер-ху) до южной границы поля (снизу). В ответе укажите два числа: сначала максимальную сумму, за-тем минимальную. Исходные данные записаны в файле 18-121.xls в виде электронной таблице размером N?N, каждая ячейка которой соответствует клетке квадрата. 119) (А. Кабанов) Квадрат разлинован на N?N клеток (1 < N < 20). Исполнитель Буквоед может пере-мещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы квадрата, обозначенные жирными линиями, Буквоед разрушается. В каждой клетке квадрата записано число от 10 до 99 или латинская буква P. Посетив клетку, Буквоед платит за её посещение, плата равна значению числа в клетке; это также относится к начальной и конечной точке маршрута. За посещение клетки P плата не взимается. Определите минимальную и максимальную плату, которую заплатит Буквоед, пройдя из левой верхней клетки в правую нижнюю, при этом маршрут должен проходить через две клетки P. В ответе укажите два числа – сначала минимальную, затем максимальную плату. Исходные данные записаны в файле 18-119.xls в виде электронной таблице размером N?N, каждая ячейка которой соответствует клетке квадрата.