Задание №18.

ЕГЭ-2024. Задание № 18

Условие задачи:

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

Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

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

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

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

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

Решение:

Найдем итоговые клетки в нашем лабиринте. Это L20, R15 и T20.

Для решения задачи, создадим (скопируем) ниже подобную таблицу, начиная со строки 22, выделим всю скопированную таблицу и нажмем клавишу DEL. Данные из таблицы будут удалены, а стены останутся. Выделим области таблицы, которые будут заполняться особым способом.

1  шаг. Заполним первый столбец таблицы (я сдвинула всю таблицу на один столбец вправо, поэтому первым столбцом у меня будет B22: B41). В ячейке В22 будет выражение (формула): =В1, в ячейке В23: =В22 + В2 и т.д.

2 шаг. заполним первую строку таблицы (строка С22:U22). Формула в ячейке С22: =В22 + С1 и т.д.

3 шаг. Все клетки таблицы (не "занятые" стрелками) при нахождении максимальной суммы заполняются так: 

Стрелка  вправо означает, что Робот в эти ячейки мможет попасть только при движении слева и формула в этих ячейках будет такой:

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

Маленький совет: Заполните сначала особые зоны таблицы, а затем - остальные ячейки, используя приемы автозаполнения.

При заполнении остальных ячеек, информация в уже заполненных ячейках будет меняться!

В трех угловых клетках три числа, максимальное из них: 2167.

Для нахождения минимального значения необходимо применить прием: НАЙТИ - ЗАМЕНИТЬ. Для получения нужного окна диалога нажмем клавиши: Ctrl + F. 

Нажмем клавишу Заменить все. Получили следующую страницу:

Из трех контрольных точек меньшее значение получим 718.

Ответ: 2167; 718.

Задачи для самостоятельного решения

Задание 18. Вариант 1 (Евич Л.Н.) файл

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

Между соседними клетками квадрата также могут быть внутренние стены.  Сквозь стену Рqбот пройти не может.

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

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

Задание 18. Вариант 5 (Евич Л.Н.) файл

Прямоугольник разлинован на М х N клеток. Исполнитель Робот может перемешаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или прыжок. По команде вправо Робот перемешается в соседнюю правую клетку, по команде прыжок - в самую левую клетку, находящуюся на один ряд ниже от текущего положения Робота. При попытке выхода за границу прямоугольника Робот разрушается.

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

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

Задание 18. Вариант 5 (Ушаков Д.М.) файл

В магазине подарков имеется некоторое количество подарков N (4 < N < 200). Каждый подарок имеет некоторую стоимость (натуральное число не более 10 000). Вася планирует купить в магазине два подарка, потратив на них сумму денег не более чем K (100 < K < 20 000). При этом цена подарков должна быть разная. Определить, сколькими способами он может это сделать, если K = 5000, и если K = 15 000.

В ответе укажите два числа — количество способов купить подарки на сумму не более 5000, и количество способов купить подарки на сумму не более чем 15 000.

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

Решение заданий № 18 ЕГЭ прошлых лет

Задание №18 можно выполнять как в среде ЭТ (электронных таблиц), так и языком программирования.

Условие задания:

Разбор алгоритма решения задания №18 (в pdf-формате).