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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу добраться до любой заданной финальной клетки.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в любую заданную финальную клетку.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу добраться до любой заданной финальной клетки.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в любую заданную финальную клетку.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу добраться до любой заданной финальной клетки.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу гарантированно прийти в любую заданную финальную клетку.

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

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

Определите: 1) минимальный начальный запас энергии, который позволит Роботу прийти в какую-нибудь финальную клетку; 2) минимальный начальный запас энергии, который позволит Роботу добраться до любой заданной финальной клетки.

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

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

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

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

(А. Богданов) Квадрат разлинован на 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 в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.