Задача к ЕГЭ по информатике на тему «прочие прототипы» №2

Квадрат разлинован на $N × N$ клеток $(2 < N < 19)$ . В каждой клетке лежат монеты, количество которых соответствует записанному числу. Количество монет не может быть меньше 1.

Два исполнителя – ВЕРХ и НИЗ – существуют на одинаковых полях. Первый имеет две команды – вверх и вправо, второй – вниз и вправо, которые, соответственно, перемещают исполнитель на одну клетку вверх, вниз или вправо. Исполнитель ВЕРХ начинает движение в левой нижней ячейке, исполнитель НИЗ – в левой верхней.

Откройте файл. Какой из исполнителей соберет большее количество монет в результате своей работы, если известно, что каждый из них запрограммирован собрать максимальное количество монет?

В ответе запишите модуль разницы между максимальной суммой, которую может собрать исполнитель НИЗ, и максимальной суммой, которую может собрать исполнитель ВЕРХ.

Нам дано поле 14 на 14, создадим рядом еще одно поле такого же размера (ячейки $A16 : N 29$ ). Сначала найдем максимальную сумму для исполнителя НИЗ.

В левую верхнюю клетку нового поля, записываем значение из левой верхней клетки исходного поля – 45.

Заполним значениями верхнюю строку. Для этого к значенею из левой верхней клетки нового поля, прибавим значение из клетки $B1$ , сделаем это с помощью формулы:

=A16+B1

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

Найдем максимальное значение суммы. Рассмотрим ячейку $B2$ , в нее мы можем попасть из $B1$ и $A2$ , тогда, чтобы в этой клетке суммы была максимальной, необходимо выбрать максимальную сумму из тех двух клеточек, из которых можем попасть в эту. В ячейку $B17$ запишем формулу:

=МАКС(A17;B16)+B2

Теперь растянем эту формулу на все свободные ячейки поля. В правом нижнем углу будет число, которое является максимальной суммой, которую может собрать исполнитель НИЗ – 2065.

Теперь найдем максимальную сумму, которую может собрать исполнитель ВЕРХ. Для этого будем использовать уже созданное поле (ячейки $A16 : N 29$ ), отчистим его.

В левую нижнюю ячейку нового поля, записываем значение из левой нижнец клетки исходного поля – 84.

Заполним значениями нижнюю строку и левый столбец. Сделаем это по аналогии с тем как мы заполняли верхнюю строку и левый столбец в решении для исполнителя НИЗ.

Найдем максимальное значение суммы. Рассмотрим ячейку $B13$ , в нее мы можем попасть из $B14$ и $A13$ , тогда, чтобы в этой клетке суммы была максимальной, необходимо выбрать максимальную сумму из тех двух клеточек, из которых можем попасть в эту. В ячейку $B28$ запишем формулу:

=МАКС(A28;B29)+B13

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

Тогда ответ будет 2065 — 2064 = 1.

Ответ: 1