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

(В. Шубинкин) Виртуальный исполнитель Варя живёт на клеточном поле размером 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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