ЕГЭ-18. Обработка целочисленных данных в электронных таблицах (динамическое программирование)

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-184.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(А. Рогов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-183.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-182.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(ЕГЭ-2023) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые

накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

Исходные данные записаны в файле 18-181.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(ЕГЭ-2023) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые

накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

Исходные данные записаны в файле 18-180.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(ЕГЭ-2023) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

Исходные данные записаны в файле 18-179.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала минимальную сумму, затем максимальную.

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-178.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вниз. По команде влево Робот перемещается в соседнюю левую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из правой верхней клетки в левую нижнюю.

Исходные данные записаны в файле 18-177.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(Е. Джобс) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-176.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-175.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

(А. Богданов) Исполнитель Робот может перемещаться по клетчатому полю, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Поле ограничено внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-174.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исполнитель Робот стоит в правом верхнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вниз. По команде влево Робот перемещается в соседнюю левую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из правой верхней клетки поля в левую нижнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.

Пример входных данных:

При указанных входных данных минимальное значение получится при движении по маршруту 12 → 8 → 11 → 23 → 17 → 19 → 41. Расход энергии на этом пути равен

12 + (12 – 8) + (11 – 8) + (23 – 11) + (23 – 17) + (19 – 17) + (41 – 19) = 61.

Максимальное значение получится при движении по маршруту 12 → 48 → 11 → 26 → 7 → 17 → 41, расход энергии в этом случае равен 153. Ответ: 61 153.

Исходные данные записаны в файле 18-170.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.

Исполнитель Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх — в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из правой нижней клетки поля в левую верхнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.

Пример входных данных:

При указанных входных данных минимальное значение получится при движении по маршруту 3 → 14 → 19 → 17 → 23 → 18 → 31. Расход энергии на этом пути равен

3 + (14 – 3) + (19 – 14) + (19 – 17) + (23 – 17) + (23 – 18) + (31 – 18) = 45.

Максимальное значение получится при движении по маршруту 3 → 30 → 8 → 11 → 48 → 18 → 31, расход энергии в этом случае равен 135. Ответ: 45 135.

Исходные данные записаны в файле 18-170.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.

Исполнитель Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из левой нижней клетки поля в правую верхнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.

Пример входных данных:

При указанных входных данных минимальное значение получится при движении по маршруту 41 → 19 → 17 → 23 → 11 → 8 → 12. Расход энергии на этом пути равен

41 + (41 – 19) + (19 – 17) + (23 – 17) + (23 – 11) + (11 – 8) + (12 – 8) = 90.

Максимальное значение получится при движении по маршруту 41 → 7 → 17 → 26 → 11 → 48 → 12, расход энергии в этом случае равен 182. Ответ: 90 182.

Исходные данные записаны в файле 18-170.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.

Исполнитель Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из левой верхней клетки поля в правую нижнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.

Пример входных данных:

При указанных входных данных минимальное значение получится при движении по маршруту 31 → 18 → 23 → 17 → 19 → 14 → 3. Расход энергии на этом пути равен

31 + (31 – 18) + (23 – 18) + (23 – 17 ) + (19 – 17) + (19 – 14) + (14 – 3) = 73.

Максимальное значение получится при движении по маршруту 31 → 18 → 48 → 12 → 8 → 30 → 3, расход энергии в этом случае равен 163. Ответ: 73 163.

Исходные данные записаны в файле 18-170.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-169.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа — сначала максимальную сумму, которую может собрать Робот, затем минимальную.

*Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вверх или по диагонали вправо вверх. Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вверх – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую верхнюю клетку поля. Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.

Пример входных данных:

Оптимальный маршрут проходит через клетки с монетами достоинством 13, 33, 50, 74, 66 (сумма 236). Все клетки, выделенные фоном, недоступны для Робота из-за ограничений.

Исходные данные записаны в файле 18-167.xls в виде электронной таблице, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: максимальную денежную сумму, которую может собрать Робот, затем количество клеток поля, недоступных Роботу.

*Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вниз – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую нижнюю клетку поля. Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.

Пример входных данных:

Оптимальный маршрут проходит через клетки с монетами достоинством 35, 10, 87, 33, 23, 35 (сумма 223). Клетки с монетами достоинством 13, 40 и 66 недоступны для Робота из-за ограничений.

Исходные данные записаны в файле 18-167.xls в виде электронной таблице, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: максимальную денежную сумму, которую может собрать Робот, затем количество клеток поля, недоступных Роботу.

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки верхней строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в одну из трёх соседних клеток следующей строки: вниз, вниз и влево или вниз и вправо. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите маршрут Робота, при котором он соберёт максимальную денежную сумму.

Исходные данные записаны в файле 18-166.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа: максимальную возможную денежную сумму, которую может собрать Робот, затем количество собранных при этом монет с чётным значением.

(PRO100 ЕГЭ) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из четырёх команд: вправо на одну клетку, вправо на две клетки, вниз на одну клетку или вниз на две клетки. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

Исходные данные записаны в файле 18-165.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе укажите два числа: сначала максимальную сумму, которую может собрать Робот, затем минимальную.