Задание №18 ЕГЭ Информатика с ответом и решением
Ответ: 323
Условие
Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз (влево и вверх ладья ходить не может). Необходимо переместить ладью в правый нижний угол так, чтобы сумма чисел в клетках, в которых ладья останавливалась (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4 × 4):
| −3 | 1 | −3 | −4 |
|---|---|---|---|
| −4 | −4 | −2 | 2 |
| 6 | 1 | 2 | −2 |
| −6 | 7 | 6 | −3 |
Для указанных входных данных ответом будет число 14 (ладья проходит через клетки с числами −3, 6, 1, 7, 6, −3).
Подсказки — как подойти к решению
- За один ход ладья проходит любое число клеток вправо или вниз, поэтому в клетку можно попасть из любой клетки той же строки слева или того же столбца сверху. Опорой служит максимум по всей строке и всему столбцу.
- Не путай ладью с Роботом, который шагает в соседнюю клетку: здесь рассматривается максимум всего префикса строки и столбца. Числа могут быть отрицательными, поэтому сумма бывает и небольшой.
Решение
Скопируем число из ячейки A1 в ячейку P1. Поскольку ладья может ходить через неограниченное количество ячеек вниз и вправо, необходимо для каждой ячейки выбирать, из какого числа в строке до этой ячейки, и из какого числа в столбце выше этой ячейки должна сходить ладья, чтобы сумма ячеек при этом была максимальной. Для этого в ячейке Q1 запишем формулу =МАКС($P$1:P1)+B1 и скопируем её во все ячейки диапазона R1:AD1. В ячейке P2 запишем формулу =МАКС($P$1:P1)+A2 и скопируем её во все ячейки диапазона P3:P15. В ячейке Q2 запишем формулу =МАКС($P2:P2;Q$1:Q1)+B2 и скопируем её во все ячейки диапазона Q2:AD15. Получим ответ — 323.
Ответ: 323.
Типичные ошибки
- Похоже, разрешён ход только в соседнюю клетку, а ладья перескакивает сколько угодно клеток: в каждой клетке нужен максимум по всей строке слева и всему столбцу сверху.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №18 по информатике