Карточки
Тесты
Главная
Курсы
Подписка
18. Исполнитель Робот: #297231
Квадрат разлинован на $N\times N$ клеток, где $1<N<26$. Исполнитель Робот может перемещаться по клеткам, выполняя одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке пересечь границу Робот разрушается.
Перед запуском в каждой клетке лежит монета достоинством от $1$ до $100$. Посетив клетку, Робот забирает монету с собой. Это относится также к начальной и конечной клеткам маршрута.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите сначала максимальную сумму, затем минимальную.
Пример входных данных:
В исходном файле таблица занимает диапазон $A1:T20$, поэтому размер квадрата равен $N=20$. Внутренних стен в таблице нет.
Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.
В ячейку $V1$ запишем: $=A1$
В ячейку $W1$: $=V1+B1$
Скопируем формулу вправо до $AO1$.
В ячейку $V2$ запишем: $=V1+A2$
Скопируем формулу вниз до $V20$.
Для поиска максимальной суммы в ячейку $W2$ запишем: $=B2+МАКС(W1;V2)$
Скопируем формулу в диапазон $W2:AO20$.
Для первых клеток:
$V1=25$,
$W1=25+25=50$,
$V2=25+20=45$,
$W2=24+\max(50;45)=74$.
В ячейке $AO20$ получим максимальную сумму: $918$.
Для поиска минимальной суммы заменим функцию МАКС на МИН. В ячейку $W2$ запишем: $=B2+МИН(W1;V2)$ и скопируем формулу в диапазон $W2:AO20$.
Для первых клеток: $W2=24+\min(50;45)=69$.
В ячейке $AO20$ получим минимальную сумму: $825$.
Ответ: $918$ $825$.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-21.csv, результат можно проверить программой:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-21.csv').read().splitlines()
)
N = len(s)
mn = [[0] * N for _ in range(N)]
mx = [[0] * N for _ in range(N)]
mn[0][0] = mx[0][0] = s[0][0]
for j in range(1, N):
mn[0][j] = mn[0][j - 1] + s[0][j]
mx[0][j] = mx[0][j - 1] + s[0][j]
for i in range(1, N):
mn[i][0] = mn[i - 1][0] + s[i][0]
mx[i][0] = mx[i - 1][0] + s[i][0]
for i in range(1, N):
for j in range(1, N):
mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])
print(mx[-1][-1], mn[-1][-1])Программа выводит: $918$ $825$.
20
