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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом до любой финальной клетки.

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

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

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

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

Определите 1) количество различных маршрутов из исходной точки в левый нижний угол поля; 2) количество клеток поля, недоступных для Робота из-за ограничения на допустимый перепад высот.

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

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

Определите 1) количество различных маршрутов из исходной точки в правый нижний угол поля; 2) количество клеток поля, недоступных для Робота из-за ограничения на допустимый перепад высот.

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

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

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

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

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

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

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

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

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

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

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

(ЕГЭ-2024) Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

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

(ЕГЭ-2024) Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

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

(ЕГЭ-2024) Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

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

(ЕГЭ-2024) Исполнитель Робот стоит в левом верхнем углу поля, разлинованного на клетки. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.

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

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

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

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

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

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

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

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

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

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