Задание 18. Информатика. 2022-5

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

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

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

1884
10113
13122
2356

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

2741

Файлы с данными

Решение:

На экзамене рекомендуется решать это задание с помощью табличного процессора.

Python

Границы необходимо вручную добавить в кортеж кортежей boundary. Каждый кортеж внутри boundary имеет вид \( (m , \,\, n) \), где \( m \) — номер ячейки с границей, а \( n \) — номер ячейки, из которой нельзя попасть в ячейку с номером \( m \). Например, \( ( 14, \,\, 10 ) \) означает, что в ячейку с номером \( 14 \) нельзя попасть из ячейки с номером \( 10 \).


from math import sqrt

# table = [1, 8, 8, 4, 10, 1, 1, 3, 1, 3, 12, 2, 2, 3, 5, 6]
# boundary = ((6, 5),)

table = []
f = open('18var5.csv')
s = f.readline()

while s:
   table += list(map(int, s.split(',')))
   s = f.readline()


boundary=((100, 84), (101, 85), (102, 86), (103, 87), (104, 88), (105, 89))

N = int(sqrt(len(table)))

table_min = [0] * (N ** 2)
table_max = [0] * (N ** 2)

table_min[0] = table[0]
table_max[0] = table[0]

for i in range(1, N):
    table_min[i] = table_min[i-1] + table[i]
    table_max[i] = table_max[i-1] + table[i]
    table_min[i*N] = table_min[(i-1)*N] + table[i*N]
    table_max[i*N] = table_max[(i-1)*N] + table[i*N]

for i in range(1, N):
    for k in range(1, N):
        v_vert = table_min[(k-1)*N+i] + table[k*N+i] if (k*N+i, (k-1)*N+i) not in boundary else 1000000
        v_hor = table_min[k*N+i-1] + table[k*N+i] if (k*N+i, k*N+i-1) not in boundary else 1000000
        table_min[k*N + i] = min(v_vert, v_hor)
        v_vert = table_max[(k-1)*N+i] + table[k*N+i] if (k*N+i, (k-1)*N+i) not in boundary else -1000000
        v_hor = table_max[k*N+i-1] + table[k*N+i] if (k*N+i, k*N+i-1) not in boundary else -1000000
        table_max[k*N + i] = max(v_vert, v_hor)

print(table_min[-1], table_max[-1])

Ответ: \(517\)    \(750\)