Question

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

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

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

*Пример входных данных:*

| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |

Для указанных входных данных ответом должна быть пара чисел 41 и 22.

Accepted Answer

1204502

Answer

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

Поскольку робот может двигаться только вправо или вниз, каждая клетка может быть достигнута только из клетки слева или сверху. Для каждой клетки $(i, j)$ вычислим максимальную (минимальную) сумму, которую можно собрать, дойдя до этой клетки.

Заполнение таблицы динамики:
- Для первой строки: каждая ячейка содержит сумму всех ячеек слева плюс текущая ячейка.
- Для первого столбца: каждая ячейка содержит сумму всех ячеек сверху плюс текущая ячейка.
- Для остальных ячеек: берём максимум (или минимум) из значений слева и сверху, прибавляем текущую ячейку.

```python
s = tuple(
    tuple(int(x) for x in m.split(';'))
    for m in open('18_demo.csv').read().splitlines()
)
N = len(s)

for f in [lambda a, b: max(a, b), lambda a, b: min(a, b)]:
    m = [[0 for _ in range(N)] for _ in range(N)]
    m[0][0] = s[0][0]
    
    for i in range(1, N):
        m[0][i] = s[0][i] + m[0][i - 1]
        m[i][0] = s[i][0] + m[i - 1][0]
    
    for row in range(1, N):
        for column in range(1, N):
            m[row][column] = (
                s[row][column] +
                f(m[row - 1][column], m[row][column - 1])
            )
    
    print(m[N - 1][N - 1], end='')
```

Сложность: $O(N^2)$.

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