Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

18. Исполнитель Робот: Конечной считается «угловая» клетка, которая ограничена стенами справа и…

Задание #297223
Решено верно
Решено неверно
Сообщить о проблеме

Квадрат разлинован на $N\times N$ клеток, где $1<N<30$. Робот может выполнять только команды вправо и вниз. Между соседними клетками могут находиться стены, через которые пройти нельзя.

В каждой клетке лежит монета достоинством от $1$ до $100$. Робот забирает монеты во всех посещённых клетках, включая начальную и конечную.

Конечной считается «угловая» клетка, которая ограничена стенами справа и снизу. Таких клеток может быть несколько. Требуется определить максимальную и минимальную суммы среди всех возможных маршрутов из левой верхней клетки в одну из конечных. В ответе сначала указывается максимальная сумма, затем минимальная.

Пример входных данных:

В исходном файле таблица занимает диапазон $A1:T20$, поэтому $N=20$.

Внутренние вертикальные стены расположены справа от диапазонов $B3:B6$, $I3$, $M4:M10$, $K8:K14$, $S8:S14$, $C14:C17$, $Q17:Q20$. Горизонтальные стены расположены снизу от $F2:I2$, $N3:Q3$, $C6:G6$, $H14:K14$, $Q14:S14$, $M16:Q16$, $D17:H17$.

Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$.

В ячейку $V1$ запишем: $=A1$

В ячейку $W1$: $=V1+B1$

Скопируем вправо до $AO1$.

В ячейку $V2$: $=V1+A2$

Скопируем вниз до $V20$.

Для поиска максимальной суммы в $W2$ запишем: $=B2+МАКС(W1;V2)$ и скопируем в диапазон $W2:AO20$.

Для первых клеток получаем:

$V1=51$,
$W1=51+9=60$,
$V2=51+11=62$,
$W2=90+\max(60;62)=152$.

Теперь учитываем стены. В клетках сразу справа от вертикальной стены оставляем только переход сверху. Такие формулы нужны в диапазонах $X3:X6$, $AE3$, $AG8:AG14$, $AO8:AO14$, $Y14:Y17$, $AM17:AM20$.

Например, в $X3$: $=C3+X2$ а в $AG8$: $=L8+AG7$.

В клетках сразу под горизонтальной стеной оставляем только переход слева. Это диапазоны $AA3:AD3$, $X7:AB7$, $AC15:AF15$, $AL15:AN15$, $AH17:AL17$, $Y18:AC18$.

Например, в $AA3$: $=F3+Z3$

В клетку $N4$ нельзя попасть ни сверху, ни слева, поэтому весь диапазон $N4:Q10$ недостижим. Для максимальной суммы в соответствующий расчётный диапазон $AI4:AL10$ можно записать большое отрицательное значение, например $-10^9$.

Конечными клетками являются $K14$, $S14$, $Q20$ и $T20$. Им соответствуют расчётные ячейки $AF14$, $AN14$, $AL20$, $AO20$.

Для них получаем максимальные суммы:

$AF14=1743$,
$AN14=1996$,
$AL20=2320$,
$AO20=2249$.

Следовательно, максимальная сумма равна: $\max(1743;1996;2320;2249)=2320$.

Для минимальной суммы в обычных клетках вместо функции МАКС используем МИН: $=B2+МИН(W1;V2)$

В недостижимый диапазон $AI4:AL10$ записываем большое положительное значение $10^9$. Формулы около стен остаются такими же.

В конечных клетках получаем:

$AF14=832$,
$AN14=1066$,
$AL20=1207$,
$AO20=1225$.

Минимальная сумма: $\min(832;1066;1207;1225)=832$.

Код на Python

Если сохранить таблицу в формате CSV с именем 18-16.csv, результат можно проверить программой:

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-16.csv').read().splitlines()
)

N = len(s)

right = set()
for r1, r2, c in [
    (3, 6, 2), (3, 3, 9), (4, 10, 13),
    (8, 14, 11), (8, 14, 19),
    (14, 17, 3), (17, 20, 17)
]:
    for r in range(r1 - 1, r2):
        right.add((r, c - 1))

down = set()
for r, c1, c2 in [
    (2, 6, 9), (3, 14, 17), (6, 3, 7),
    (14, 8, 11), (14, 17, 19),
    (16, 13, 17), (17, 4, 8)
]:
    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 == 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 and mn[i][j] < 10**9:
            ends.append((mn[i][j], mx[i][j]))

print(max(x[1] for x in ends), min(x[0] for x in ends))

Программа выводит:

$2320$ $832$

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение