ЕГЭ Информатика 2021: Задача 18 (Робот и монеты)

Квадрат разлинован на n × n клеток. Исполнитель Робот перемещается по клеткам, выполняя за одно перемещение одну из двух команд: «вправо» или «вниз». Команда «вправо» перемещает робота в соседнюю правую клетку, команда «вниз» — в соседнюю нижнюю. При выходе за границу квадрата робот разрушается.

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

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

Исходные данные — электронная таблица размером n × n, где каждая ячейка соответствует клетке квадрата. Пример — таблица 10 × 10, но размеры могут быть другими (например, 15 × 5). Задача — поиск наиболее выгодного пути для робота, перемещающегося только вправо или вниз, от левой верхней клетки к правой нижней.

Решение в Excel

Решение задачи удобно реализовать в Excel. Создадим вспомогательную таблицу под исходной.

  1. Инициализация: В первую ячейку вспомогательной таблицы запишем значение из левой верхней ячейки исходной. Например, если значение в исходной таблице равно 51, то в первую ячейку вспомогательной таблицы запишем =51.
  2. Движение вправо: В следующей ячейке вспомогательной таблицы (справа от первой) рассчитаем сумму при движении только вправо: =51 + B1 (где B1 – значение из второй ячейки первого ряда исходной таблицы). Формулу копируем вправо на всю ширину таблицы.
  3. Движение вниз: Под первой ячейкой вспомогательной таблицы рассчитаем сумму при движении только вниз: =13 + A2 (где A2 – значение из второй ячейки первого столбца исходной таблицы). Формулу копируем вниз на всю высоту таблицы.
  4. Максимальный путь: В ячейки вспомогательной таблицы между путями «только вправо» и «только вниз» впишем формулу, находящую максимальное значение из двух возможных путей: =B2 + MAX(C2; B3) (где B2 — значение текущей ячейки в исходной таблице, C2 — значение ячейки справа в вспомогательной таблице, B3 — значение ячейки снизу в вспомогательной таблице). Формулу копируем на всю вспомогательную таблицу.
  5. Определение максимальной суммы: В правом нижнем углу вспомогательной таблицы будет максимальное количество монет, которое может собрать робот.
  6. Минимальный путь: Для нахождения минимальной суммы повторяем шаги 1-5, заменив функцию MAX на MIN. В правом нижнем углу вспомогательной таблицы будет минимальное количество монет.

Ответ

Результат расчётов — два числа: максимальная и минимальная сумма монет, которые может собрать робот. Например, 1204 502. Это и будет ответом на задание 18.

Что будем искать? Например,программа