Задание 18. Информатика. 2022-2
- Просмотры: 126
- Изменено: 23 ноября 2024
Квадрат разлинован на \(N \times N\) клеток \( ( 1 < N < 20)\). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, а по команде вниз — в соседнюю нижнюю. При попытке пересечь границы (внутренние и границы квадрата) Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от \(1\) до \(100\). Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером \( N \times N\), каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
| 1 | 5 | 8 | 4 |
| 10 | 1 | 10 | 3 |
| 1 | 3 | 1 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел:
| 36 | 24 |
Решение:
На экзамене рекомендуется решать это задание с помощью табличного процессора.
Python
Границы необходимо вручную добавить в кортеж кортежей boundary. Каждый кортеж внутри boundary имеет вид \( (m , \,\, n) \), где \( m \) — номер ячейки с границей, а \( n \) — номер ячейки, из которой нельзя попасть в ячейку с номером \( m \). Например, \( ( 14, \,\, 10 ) \) означает, что в ячейку с номером \( 14 \) нельзя попасть из ячейки с номером \( 10 \).
from math import sqrt
# table = [1, 5, 8, 4, 10, 1, 10, 3, 1, 3, 1, 2, 2, 3, 5, 6]
# boundary = ((10,9),)
table = []
f = open('18var2.csv')
s = f.readline()
while s:
table += list(map(int, s.split(',')))
s = f.readline()
boundary=((43, 42), (63, 62), (83, 82), (103, 102), (123, 122), \
(226, 225), (246, 245), (266, 265), (286, 285))
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_max[-1], table_min[-1])
Ответ: \(721\) \(559\)