Задание 18. Динамика в электронных таблицах

Задание 18 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Файл к заданию: demo_18.ods – скачайте его и повторяйте шаги разбора в LibreOffice.

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

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

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

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

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

На рисунке поле 4 × 4 – это только иллюстрация формата данных, настоящее поле в файле 20 × 20.

1. В клетку можно прийти только слева или сверху – других команд у Робота нет. Значит лучшая сумма в клетке = лучшая из двух соседних плюс монета этой клетки, и всё поле считается одним проходом сверху вниз. Перебирать маршруты не нужно и невозможно: их у поля 20 × 20 астрономически много.
2. Стена меняет ровно одно: у клетки за стеной один из двух входов закрыт, и лишний аргумент убирают из её формулы. Все эти клетки устроены двумя способами – стена сверху или стена слева. Значит и правок будет две: одну исправленную формулу размножают по всем клеткам под стенами, вторую – по всем клеткам справа от стен.
3. Маршрут кончается не в правом нижнем углу, а в конечной клетке – той, у которой закрыты и право, и низ.
4. Максимум и минимум – одна таблица, посчитанная дважды. Сначала считаем максимум и записываем его, потом меняем во всех формулах МАКС на МИН и снимаем минимум с тех же клеток.

В четырёх отмеченных клетках стоят итоговые суммы всех маршрутов, какие может пройти Робот. До замены МАКС на МИН в них максимумы, после – минимумы:

Ответ: 2598 803 – сначала максимальная сумма, потом минимальная.

• Ответили по правой нижней клетке. T20 – тоже конечная клетка, но не единственная.
• Не заметили стен. Неправильно перенесли форматирование или после вставки формул потеряли стенку.
• Оставили формулы в недостижимой области. МАКС и МИН от двух пустых ячеек возвращают 0, и через N4:Q10 «протекает» маршрут ценой в одну монету: минимум становится 467.
• Записали ответ не в том порядке. Сначала максимальная сумма, потом минимальная (читайте условие внимательно).