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

18. Исполнитель Робот: Между соседними клетками могут быть стены, через которые пройти нельзя

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

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

В каждой клетке лежит монета достоинством от $1$ до $100$. Посетив клетку, Робот забирает монету с собой; это относится и к начальной, и к конечной клеткам маршрута.

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

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

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

Вертикальные внутренние стены расположены справа от клеток $R3:R5$, $J4:J8$, $D7:D9$, $R10:R18$, $E12:E18$ и $J14:J18$. Горизонтальные стены расположены снизу от $G3:J3$, $O5:R5$, $B9:D9$, $G13:J13$, $D18:E18$ и $L18:R18$.

Расчётную таблицу разместим справа от исходной, начиная с ячейки $V1$. В ячейку $V1$ запишем $=A1$. В ячейку $W1$ запишем $=V1+B1$ и скопируем вправо до $AO1$. В ячейку $V2$ запишем $=V1+A2$ и скопируем вниз до $V20$.

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

Для первых клеток получаем: $V1=52$, $W1=52+1=53$, $V2=52+78=130$, $W2=36+\max(53;130)=166$.

После этого исправим формулы около стен. Справа от вертикальной стены в клетку можно попасть только сверху. Поэтому для диапазонов $S3:S5$, $K4:K8$, $E7:E9$, $S10:S18$, $F12:F18$ и $K14:K18$ используем только значение верхней клетки. Например, в $AN3$ запишем $=S3+AN2$ и скопируем до $AN5$, а в $AF4$ — $=K4+AF3$ и скопируем до $AF8$.

В клетки под горизонтальными стенами можно попасть только слева. Это диапазоны $G4:J4$, $O6:R6$, $B10:D10$, $G14:J14$, $D19:E19$ и $L19:R19$. Например, в $AB4$ запишем $=G4+AA4$ и скопируем вправо до $AE4$.

Конечными являются клетки $R5$, $D9$, $E18$, $R18$ и $T20$. Им соответствуют расчётные ячейки $AM5$, $Y9$, $Z18$, $AM18$ и $AO20$.

Максимальные накопленные суммы в них равны соответственно $1285$, $794$, $1347$, $2353$ и $2507$. Следовательно, максимальная сумма равна $\max(1285;794;1347;2353;2507)=2507$.

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

Минимальные суммы в конечных клетках равны $753$, $366$, $1036$, $1117$ и $1479$. Следовательно, минимальная сумма равна $\min(753;366;1036;1117;1479)=366$.

Код на Python

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

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

N = len(s)

right = set()
for r1, r2, c in [
    (3, 5, 18), (4, 8, 10), (7, 9, 4),
    (10, 18, 18), (12, 18, 5), (14, 18, 10)
]:
    for r in range(r1 - 1, r2):
        right.add((r, c - 1))

down = set()
for r, c1, c2 in [
    (3, 7, 10), (5, 15, 18), (9, 2, 4),
    (13, 7, 10), (18, 4, 5), (18, 12, 18)
]:
    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_right = j == N - 1 or (i, j) in right
        wall_down = i == N - 1 or (i, j) in down

        if wall_right and wall_down:
            ends.append((mn[i][j], mx[i][j]))

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

Программа выводит: $2507$ $366$.

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

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