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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(Е. Джобс) Квадрат разлинован на N×N клеток (2 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается, при столкновении со стеной робот разрушается. В каждой клетке записано число – количество монет, которое необходимо заплатить за проход. Если число отрицательное – счёт робота уменьшается, если положительное – увеличивается. Начальным значением счёта является значение стартовой клетки. Определите максимальное значение счета робота при движении из левой нижней клетки поля в правую верхнюю, если:

А) роботу запрещено перемещаться при отрицательном счёте,

Б) робот может перемещаться при отрицательном счёте.

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

(Е. Джобс) Квадрат разлинован на N×N клеток (2 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается, при столкновении со стеной робот разрушается. Также робот перемещается вдоль стен, то есть может переместиться только в ту клетку, в которой есть стена. Перед каждым запуском Робота в каждой клетке квадрата записано число от 10 до 99. Посетив клетку Робот прибавляет к своему счету записанное в ней значение. Определите максимальное и минимальное значение счета, который может набрать Робот, пройдя из левой нижней клетки в правую верхнюю.

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

(Е. Джобс) Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое положительное число – количество монет. Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначены жирной линией, через которые Сборщик проходить не может. Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней. Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной?

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

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

A) максимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю;

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

Исходные данные записаны в файле 18-114.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.

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

A) максимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю;

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

Исходные данные записаны в файле 18-113.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом нижнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из правого нижнего угла в левый верхний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом нижнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из левого нижнего угла в правый верхний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо или на одну клетку вниз. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-109.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.

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

A) запрещено спешиваться;

B) разрешено спешиваться.

Исходные данные записаны в файле 18-108.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.

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

A) запрещено спешиваться;

B) разрешено спешиваться.

Исходные данные записаны в файле 18-107.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В правом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку влево, вниз или по диагонали влево-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из правого верхнего угла в левый нижний. Исходные данные записаны в файле 18-105.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.

Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом верхнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо, вниз или по диагонали вправо-вниз. Определите минимальную и максимальную сумму чисел в клетках, через которые может пройти Робот при перемещении из левого верхнего угла в правый нижний. Исходные данные записаны в файле 18-105.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, потом минимальную.