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

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

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

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

При указанных входных данных минимальное значение получится при движении по маршруту 3 → 14 → 19 → 17 → 23 → 18 → 31. Расход энергии на этом пути равен

3 + (14 – 3) + (19 – 14) + (19 – 17) + (23 – 17) + (23 – 18) + (31 – 18) = 45.

Максимальное значение получится при движении по маршруту 3 → 30 → 8 → 11 → 48 → 18 → 31, расход энергии в этом случае равен 135. Ответ: 45 135.

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

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

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

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

При указанных входных данных минимальное значение получится при движении по маршруту 41 → 19 → 17 → 23 → 11 → 8 → 12. Расход энергии на этом пути равен

41 + (41 – 19) + (19 – 17) + (23 – 17) + (23 – 11) + (11 – 8) + (12 – 8) = 90.

Максимальное значение получится при движении по маршруту 41 → 7 → 17 → 26 → 11 → 48 → 12, расход энергии в этом случае равен 182. Ответ: 90 182.

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

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

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

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

При указанных входных данных минимальное значение получится при движении по маршруту 31 → 18 → 23 → 17 → 19 → 14 → 3. Расход энергии на этом пути равен

31 + (31 – 18) + (23 – 18) + (23 – 17 ) + (19 – 17) + (19 – 14) + (14 – 3) = 73.

Максимальное значение получится при движении по маршруту 31 → 18 → 48 → 12 → 8 → 30 → 3, расход энергии в этом случае равен 163. Ответ: 73 163.

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

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

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

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

*Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вверх или по диагонали вправо вверх. Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вверх – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую верхнюю клетку поля. Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.

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

Оптимальный маршрут проходит через клетки с монетами достоинством 13, 33, 50, 74, 66 (сумма 236). Все клетки, выделенные фоном, недоступны для Робота из-за ограничений.

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

*Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вниз – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую нижнюю клетку поля. Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.

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

Оптимальный маршрут проходит через клетки с монетами достоинством 35, 10, 87, 33, 23, 35 (сумма 223). Клетки с монетами достоинством 13, 40 и 66 недоступны для Робота из-за ограничений.

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

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

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

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

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

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

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

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

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

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

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

(Г. Золотухин) Квадрат разлинован на N×N клеток (1 < N < 20). В каждой клетке находится некоторое количество монет, от 1 до 100. Исполнитель «Конь» движется с левой линии в правую линию. т. е. он может стартовать из любой клетки первого столбца и закончить маршрут в любой клетке последнего столбца таблицы. С каждой посещённой клетки исполнитель забирает с собой половину монет, если количество монет нечётное, то округление происходит в большую сторону.

Исполнитель может двигаться «ходом коня»: на две клетки вправо и на одну вверх или вниз, или на одну клетку вправо и на две клетки вверх или вниз. Определите максимальную и минимальную суммы, которые может собрать исполнитель.

Пример входных данных (для таблицы размером 5×5):

Для данного примера максимальная сумма получается при проходе коня по клеткам со значениями 54, 98, 46, 75 и 55; эта сумма равна 27+49+23+38+28=165. Минимальная сумма получается при проходе коня по клеткам со значениями 16, 46 и 15; эта сумма равна 8+23+8=39.

Ответ: 165 39.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 51 + 39 + 11 + 2 + 56 = 159. При этом робот проходит через 3 клетки с нечётными числами (51, 39, 11). В ответе в данном случае надо записать числа 159 и 3.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вверх, по диагонали влево-вверх или по диагонали вправо-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 68 + 46 + 11 + 26 = 151. При этом робот проходит через 3 клетки с чётными числами (68, 46, 26). В ответе в данном случае надо записать числа 151 и 3.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вниз, по диагонали влево-вниз или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 56 + 2 + 11 + 39 + 51 = 159. При этом робот проходит через 2 клетки с чётными числами (56, 2). В ответе в данном случае надо записать числа 159 и 2.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали вправо-вверх. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных минимальный расход получится при движении по маршруту 26 + 11 + 46 + 68 = 151. При этом робот проходит через 1 клетку с нечётным числом (11). В ответе в данном случае надо записать числа 151 и 1.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали вправо-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 51 + 89 + 24 + 39 + 12 + 46 + 68 + 38 + 41 + 56 = 464. При этом робот проходит через 4 клетки с нечётными числами (51, 89, 39, 41). В ответе в данном случае надо записать числа 464 и 4.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вверх, по диагонали влево-вверх или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 68 + 38 + 41 + 56 + 15 + 39 + 51 + 89 + 18 + 26 = 441. При этом робот проходит через 5 клеток с чётными числами (68, 38, 56, 18, 26). В ответе в данном случае надо записать числа 441 и 5.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вниз, по диагонали влево-вниз или по диагонали вправо-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 56 + 2 + 44 + 15 + 38 + 46 + 39 + 89 + 24 + 51 = 404. При этом робот проходит через 6 клеток с чётными числами (56, 2, 44, 38, 46, 24). В ответе в данном случае надо записать числа 404 и 6.

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

Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз, по диагонали вправо-вниз или по диагонали влево-вниз. Числа показывают расход энергии робота на прохождение клетки.

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

количество пройденных клеток с нечётными значениями.

Пример входных данных (для таблицы размером 4×4):

При указанных входных данных максимальный расход получится при движении по маршруту 26 + 44 + 18 + 11 + 89 + 39 + 46 + 38 + 12 + 68 = 391. При этом робот проходит через 3 клетки с нечётными числами (11, 89, 39). В ответе в данном случае надо записать числа 391 и 3.

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

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с запада (левый столбец) на восток (правый столбец). Он может начать переход с любой клетки левого столбца и закончить на любой клетке правого столбца. С каждым шагом Робот переходит в следующий столбец и может за одно перемещение попасть в одну из трех клеток следующего столбца (на клетку вправо или боковые с ней, вправо-вниз или вправо-вверх). Ходы только вверх или вниз (без смены столбца) и назад (в предыдущий столбец) запрещены.

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

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