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

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

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

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

 

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

 

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

Если начальный запас энергии Робота равен 100 единиц, то для указанных входных данных ответом должна быть пара чисел: 69 102

Скачать файл

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

Перед каждым запуском Робота он обладает запасом энергии в 5000 единиц. В каждой клетке квадрата указано количество энергии, которое Робот потратит, перемещаясь в данную клетку; это также относится к начальной и конечной клеткам маршрута Робота. Некоторые клетки являются труднопроходимыми для Робота. На перемещение в них Робот тратит двойную энергию, указанную в таких клетках. Такие клетки обозначены ячейками с красным фоном.

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

 

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

 

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

 

Если начальный запас энергии Робота равен 100 единиц, то для указанных входных данных ответом должна быть пара чисел: 76 54

Скачать файл

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

Перед каждым запуском Робота он обладает запасом энергии в 5000 единиц. В каждой клетке квадрата указано количество энергии, которое Робот потратит, перемещаясь в данную клетку; это также относится к начальной и конечной клеткам маршрута Робота.

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

 

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

 

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

Если начальный запас энергии Робота равен 100 единиц, то для указанных входных данных ответом должна быть пара чисел: 79 61

Скачать файл

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

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

 

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

 

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

 

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

Скачать файл

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

 

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

 

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

 

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

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

Скачать файл

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

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

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

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


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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Файл к заданию

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

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

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

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

Скачать файл

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

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

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

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


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

Скачать файл

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

Некоторые клетки опасны для Робота. Попав в такие клетки, Робот разрушается. Обозначены  такие клетки отрицательными числами.

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл

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

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

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

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

Скачать файл