Карточки
Тесты
Главная
Курсы
Подписка
18. Исполнитель Робот: #297249
Квадрат разлинован на $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=24$,
$W1=24+25=49$,
$V2=24+20=44$,
$W2=20+\max(49;44)=69$.
В ячейке $AO20$ получим максимальную сумму: $913$.
Для поиска минимальной суммы в ячейке $W2$ используем: $=B2+МИН(W1;V2)$ и копируем формулу в диапазон $W2:AO20$.
Для первых клеток: $W2=20+\min(49;44)=64$.
В ячейке $AO20$ получим минимальную сумму: $819$.
Ответ: $913$ $819$.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-23.csv, результат можно проверить программой:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-23.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])Программа выводит: $913$ $819$.
20
