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

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

Пример входных данных (для поля 3х3):

Для указанных входных данных ответом должна быть пара чисел 47 и 15.

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

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

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

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

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

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

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

(Информатик-БУ) Квадрат разлинован на N×N клеток (1 < N < 12). Исполнитель Змейка может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Змейка перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенками, сквозь стену Змейка пройти не может. В некоторых клетках квадрата расположены двоичные цифры (0 или 1). Посетив клетку с цифрой, Змейка подставляет её к своему хвосту. Например, посетив клетку с единицей, Змейка вида «1011» превратится в «11011», а посетив клетку с нулём – в «01011». Определите максимальное и минимальное значение Змейки после того, как она пройдет из левой верхней клетки в правую нижнюю.

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

(Информатик-БУ) Квадрат разлинован на N×N клеток (1 < N < 12). Исполнитель Змейка может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Змейка перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенками, сквозь стену Змейка пройти не может. В некоторых клетках квадрата расположены двоичные цифры (0 или 1). Посетив клетку с цифрой, Змейка подставляет её к своей голове. Например, посетив клетку с единицей, Змейка вида «1011» превратится в «10111», а посетив клетку с нулём – в «10110». Определите максимальное и минимальное значение Змейки после того, как она пройдет из левой верхней клетки в правую нижнюю.

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

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

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

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

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

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

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вправо, вниз или телепорт. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю, по команде телепорт – в любую клетку ниже и/или правее той, в которой находится, кроме двух соседних клеток (т.е. исполнитель предпочитает команды вниз и вправо, если нужно перейти в соседнюю клетку). Поле ограничено внешними стенами, за которые Варя никогда не выходит. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил. Определите минимальную сумму, которую может получить Варя, а также сколько раз ей пришлось воспользоваться командой телепорт, чтобы получить эту сумму.

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

Пример входных данных для поля 5×5:

Для таких данных ответом будут числа –24 и 2 (см. карту движения исполнителя на рисунке справа).

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вправо, вниз или телепорт. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю, по команде телепорт – в любую клетку ниже и/или правее той, в которой находится, кроме двух соседних клеток (т.е. исполнитель предпочитает команды вниз и вправо, если нужно перейти в соседнюю клетку). Поле ограничено внешними стенами, за которые Варя никогда не выходит. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил. Определите максимальную сумму, которую может получить Варя, а также сколько раз ей пришлось воспользоваться командой телепорт, чтобы получить эту сумму.

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

Пример входных данных для поля 5×5:

Для таких данных ответом будут числа 7 и 1 (см. карту движения исполнителя на рисунке справа).

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Поле ограничено внешними стенами. Между соседними клетками поля также могут быть внутренние стены, сквозь стену Варя пройти не может. На поле имеются голубые клетки, с каждой из которых исполнитель может телепортироваться в любую клетку правее и/или ниже исходной голубой клетки в пределах поля. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил. Определите минимальную и максимальную сумму, которую может получить исполнитель, пройдя из верхней левой клетки в правую нижнюю.

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

Пример входных данных для поля 5×5:

На таком поле Варя из клетки B3 может перейти в любую клетку диапазона B3:E5, кроме самой клетки B3 (стены не препятствуют телепортации). Для приведённого примера ответом будут числа -20 и 3.

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Поле ограничено внешними стенами. Между соседними клетками поля также могут быть внутренние стены, сквозь стену Варя пройти не может. На поле имеется голубая клетка, с которой исполнитель может телепортироваться в любую клетку правее и/или ниже голубой в пределах поля. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил. Определите минимальную и максимальную сумму, которую может получить исполнитель, пройдя из верхней левой клетки в правую нижнюю.

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

Пример входных данных для поля 5×5:

На таком поле Варя из клетки B3 может перейти в любую клетку диапазона B3:E5, кроме самой клетки B3 (стены не препятствуют телепортации). Для приведённого примера ответом будут числа -20 и 3.

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

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

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

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

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

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

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

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

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

В начальный момент уровень заряда равен значению, указанному в левой верхней клетке поля. На зарядку робот тратит 5 минут, на выполнение одной команды вниз или вправо – 1 минуту. Определите минимальное количество минут, за которое робот сможет преодолеть лабиринт – добраться до правой нижней клетки.

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

Для такого примера ответ будет: 16 (ВНИЗ-ВНИЗ-(Зарядка)-ВНИЗ-(Зарядка)-ВПРАВА-ВПРАВО-ВПРАВО).

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

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

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

Для указанных входных данных ответом является пара чисел: 36 (путь через ячейки 10, 8, 16, 6, 7, 13, 11) и 22 (путь через ячейки 10, 8, 16, 18, 8, 10, 11).

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

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

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

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

Для указанных входных данных ответом является пара чисел: 18 36.

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

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

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

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

Для указанных входных данных ответом является пара чисел: 16 41.