Карточки
Тесты
Главная
Курсы
Подписка
18. Исполнитель Робот: #297246
Квадрат разлинован на $N\times N$ клеток, где $1<N<26$. Исполнитель Робот может перемещаться по клеткам, выполняя одну из двух команд: вправо или вниз. По команде вправо Робот переходит в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается.
Перед запуском в каждой клетке указана плата за посещение размером от $1$ до $100$. Посетив клетку, Робот платит указанную сумму. Это относится и к начальной, и к конечной клеткам маршрута.
Определите минимальную и максимальную денежные суммы, которые заплатит Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите сначала минимальную сумму, затем максимальную.
Пример входных данных:
В исходном файле таблица занимает диапазон $A1:O15$, поэтому $N=15$. Внутренних стен нет.
Расчётную таблицу разместим справа от исходной, начиная с ячейки $Q1$.
В ячейку $Q1$ запишем: $=A1$
В ячейку $R1$: $=Q1+B1$ и скопируем вправо до $AE1$.
В ячейку $Q2$: $=Q1+A2$ и скопируем вниз до $Q15$.
Для поиска минимальной суммы в $R2$ запишем: $=B2+МИН(R1;Q2)$ и скопируем формулу в диапазон $R2:AE15$.
Для первых клеток:
$Q1=22$,
$R1=22+21=43$,
$Q2=22+28=50$,
$R2=11+\min(43;50)=54$.
В ячейке $AE15$ получим минимальную сумму: $438$.
Для поиска максимальной суммы заменим функцию МИН на МАКС: $=B2+МАКС(R1;Q2)$ и скопируем формулу в диапазон $R2:AE15$.
Для первых клеток: $R2=11+\max(43;50)=61$.
В ячейке $AE15$ получим максимальную сумму: $669$.
Ответ: $438$ $669$.
Код на Python
Если сохранить таблицу в формате CSV с именем 18-24.csv, результат можно проверить программой:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-24.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(mn[-1][-1], mx[-1][-1])Программа выводит: $438$ $669$.
20
