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

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

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

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

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

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

Исходные данные представлены электронной таблицей размером $N\times N$. Внутренние и внешние стены обозначены утолщёнными линиями.

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

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

Внутренние стены расположены справа от клеток $F4:F15$ и снизу от клеток $L17:Q17$.

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

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

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

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

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

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

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

Скопируем формулу в диапазон $W2:AO20$.

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

$V1=105$,
$W1=105+85=190$,
$V2=105+86=191$,
$W2=27+\max(190;191)=218$.

Теперь учтём стены.

Из клеток $F4:F15$ нельзя перейти вправо в $G4:G15$, поэтому в соответствующие клетки можно попасть только сверху. Столбцу $G$ соответствует столбец $AB$ расчётной таблицы.

В ячейку $AB4$ запишем: $=G4+AB3$

Скопируем формулу до $AB15$.

Через стену между строками $17$ и $18$ в столбцах $L:Q$ пройти вниз нельзя. Поэтому в клетки $L18:Q18$ можно попасть только слева.

В ячейку $AG18$ запишем: $=L18+AF18$

Скопируем формулу вправо до $AL18$.

В ячейке $AO20$ получим максимальную сумму: $2852$.

Для поиска минимальной суммы используем ту же таблицу, но в ячейке $W2$ вместо максимума выбираем минимум: $=B2+МИН(W1;V2)$

Скопируем формулу в диапазон $W2:AO20$, после чего снова зададим формулы для клеток около стен: $AB4=G4+AB3$ с копированием до $AB15$, и $AG18=L18+AF18$ с копированием до $AL18$.

Для первых клеток: $W2=27+\min(190;191)=217$.

В ячейке $AO20$ получим минимальную сумму: $1784$.

Код на Python

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

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

N = len(s)

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]

# Нельзя войти слева в G4:G15
wall_left = {(i, 6) for i in range(3, 15)}

# Нельзя войти сверху в L18:Q18
wall_top = {(17, j) for j in range(11, 17)}

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) not in wall_left:
            a.append(mn[i][j - 1])
            b.append(mx[i][j - 1])

        if i > 0 and (i, j) not in wall_top:
            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)

print(mx[-1][-1], mn[-1][-1])

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

$2852$ $1784$

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

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