Задание 18. Робот-сборщик монет

01.02.2022

Задание 18. Динамическое программирование. Умение обрабатывать вещественные выражения в электронных таблицах

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

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

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

  • (№ 4223) (А. Кабанов) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Буквоед может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы квадрата, обозначенные жирными линиями, Буквоед разрушается. В каждой клетке квадрата записано число от 10 до 99 или латинская буква P. Посетив клетку, Буквоед платит за её посещение, плата равна значению числа в клетке; это также относится к начальной и конечной точке маршрута. За посещение клетки P плата не взимается. Определите минимальную и максимальную плату, которую заплатит Буквоед, пройдя из левой верхней клетки в правую нижнюю, при этом маршрут должен проходить через две клетки P. В ответе укажите два числа – сначала минимальную, затем максимальную плату. Исходные данные для Буквоеда записаны в файле 18-119.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.