Карточки
Тесты
Главная
Курсы
Подписка
18. Исполнитель Робот: #297258
Квадрат разлинован на $N\times N$ клеток, где $1<N<30$. Робот может выполнять только команды вправо и вниз. Между соседними клетками могут находиться внутренние стены, через которые пройти нельзя.
В каждой клетке лежит монета достоинством от $1$ до $100$. Посетив клетку, Робот забирает монету с собой, включая начальную и конечную клетки маршрута.
Конечной считается «угловая» клетка, у которой справа и снизу находятся стены. Таких клеток может быть несколько. Требуется определить максимальную и минимальную суммы среди всех маршрутов из левой верхней клетки в одну из конечных. В ответе сначала указывается максимальная сумма, затем минимальная.
Пример входных данных:
Исходная таблица занимает диапазон $A1:T20$, поэтому $N=20$.
Вертикальные стены расположены справа от $L2:L11$, $G4:G19$, $S5:S10$, $Q11:Q18$, $D12:D16$. Горизонтальные стены расположены снизу от $P4:S4$, $J11:L11$, $B16:D16$, $M18:Q18$, $E19:G19$.
Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.
В $V1$ запишем: $=A1$
В $W1$: $=V1+B1$ и скопируем вправо до $AO1$.
В $V2$: $=V1+A2$ и скопируем вниз до $V20$.
Для поиска максимальной суммы в $W2$ запишем: $=B2+МАКС(W1;V2)$ и скопируем в диапазон $W2:AO20$.
Для первых клеток:
$V1=24$,
$W1=24+57=81$,
$V2=24+21=45$,
$W2=75+\max(81;45)=156$.
После этого исправим формулы около стен. Справа от вертикальной стены в клетку можно попасть только сверху. Например, для $M2:M11$ в $AH2$ запишем: $=M2+AH1$ и скопируем до $AH11$.
Аналогично обрабатываем диапазоны $AC4:AC19$, $AO5:AO10$, $AM11:AM18$, $Z12:Z16$.
Под горизонтальной стеной можно попасть только слева. Например, для $P5:S5$ в $AK5$ запишем: $=P5+AJ5$ и скопируем до $AN5$.
Аналогично обрабатываем диапазоны $AE12:AG12$, $W17:Y17$, $AH19:AL19$, $Z20:AB20$.
Конечными клетками являются $L11$, $D16$, $Q18$, $G19$ и $T20$. Максимальные суммы в них равны: $1618$, $1264$, $2323$, $1597$, $2463$.
Следовательно, $\max(1618;1264;2323;1597;2463)=2463$.
Для поиска минимальной суммы в обычных клетках используем: $=B2+МИН(W1;V2)$
Для первых клеток: $W2=75+\min(81;45)=120$.
Формулы около стен остаются такими же.
Минимальные суммы в конечных клетках равны: $968$, $669$, $1211$, $819$, $1412$.
Следовательно, $\min(968;669;1211;819;1412)=669$.
Ответ: $2463$ $669$.
Код на Python
Если сохранить таблицу в формате CSV с именем 18-27.csv, результат можно проверить программой:
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-27.csv').read().splitlines()
)
N = len(s)
right = set()
for r1, r2, c in [
(2, 11, 12), (4, 19, 7), (5, 10, 19),
(11, 18, 17), (12, 16, 4)
]:
for r in range(r1 - 1, r2):
right.add((r, c - 1))
down = set()
for r, c1, c2 in [
(4, 16, 19), (11, 10, 12), (16, 2, 4),
(18, 13, 17), (19, 5, 7)
]:
for c in range(c1 - 1, c2):
down.add((r - 1, c))
mn = [[10 ** 9] * N for _ in range(N)]
mx = [[-10 ** 9] * N for _ in range(N)]
mn[0][0] = mx[0][0] = s[0][0]
for i in range(N):
for j in range(N):
if i == 0 and j == 0:
continue
a, b = [], []
if j > 0 and (i, j - 1) not in right:
a.append(mn[i][j - 1])
b.append(mx[i][j - 1])
if i > 0 and (i - 1, j) not in down:
a.append(mn[i - 1][j])
b.append(mx[i - 1][j])
if a:
mn[i][j] = s[i][j] + min(a)
mx[i][j] = s[i][j] + max(b)
ends = []
for i in range(N):
for j in range(N):
wall_r = j == N - 1 or (i, j) in right
wall_d = i == N - 1 or (i, j) in down
if wall_r and wall_d:
ends.append((mn[i][j], mx[i][j]))
print(max(x[1] for x in ends), min(x[0] for x in ends))Программа выводит: $2463$ $669$.
20
