Question

Квадратная сетка размером $N 	imes N$ клеток (1 < N < 17) содержит в каждой клетке монету достоинством от 1 до 100. Робот начинает в левой верхней клетке и может двигаться только вправо или вниз. При выходе за границы или пересечении внутренней стенки робот разбивается. Конечная остановка — клетка, ограниченная стенкой справа и снизу (робот не может продолжить движение).

Найти максимальную и минимальную суммы монет, собранные роботом от начальной до конечной клетки (включая обе).

В ответе указать два числа без пробела: сначала максимум, затем минимум.

Accepted Answer

2010613

Answer

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

**Вычисление максимальной суммы:**

1. Инициализируем первую строку: каждая ячейка содержит сумму всех монет слева от неё (включая саму ячейку).

2. Инициализируем первый столбец: каждая ячейка содержит сумму всех монет сверху от неё (включая саму ячейку).

3. Для остальных ячеек применяем правило: значение текущей ячейки равно её монете плюс максимум из значения сверху и значения слева.

4. Для ячеек, слева от которых стоит внутренняя стенка, значение вычисляется только как сумма текущей ячейки и значения сверху.

5. Для ячеек, сверху от которых стоит внутренняя стенка, значение вычисляется только как сумма текущей ячейки и значения слева.

6. Максимальная сумма — это максимум среди всех возможных конечных клеток (угловых клеток, ограниченных стенками).

**Вычисление минимальной суммы:**

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

**Реализация в электронной таблице:**

- Ячейка A18: `=СУММ($A$1:A1)` — копируется по строке 18 и столбцу A для инициализации границ.
- Ячейка B19: `=B2+МАКС(A19;B18)` — копируется на весь диапазон B19:P33 для основного расчёта.
- Для ячеек с внутренними стенками слева (например, E25:E32): `=E24+E8` — используется только значение сверху.
- Для ячеек с внутренними стенками сверху (например, B33:D33): `=A33+B16` — используется только значение слева.
- Финальная формула для максимума: `=МАКС(P33;N31;I27;D32)` — выбирает максимум среди всех конечных клеток.
- Финальная формула для минимума: `=МИН(P33;N31;I27;D32)` — выбирает минимум среди всех конечных клеток.

Результаты: максимальная сумма — 2010, минимальная сумма — 613.

Задание №18Информационные модели и структуры данныхЕГЭ по информатике