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

18. Исполнитель Робот: Исходные данные представлены электронной таблицей размером N× N, каждая…

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

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

По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

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

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

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

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

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

В таблице имеются три внутренние стены:

  • между столбцами $F$ и $G$ в строках с $4$ по $15$;
  • между столбцами $S$ и $T$ в строках со $2$ по $10$;
  • между строками $17$ и $18$ в столбцах от $L$ до $Q$.

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

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

Получим: $V1=107$.

Для первой строки в ячейку $W1$ запишем: $=V1+B1$

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

Для первого столбца расчётной таблицы в ячейку $V2$ запишем: $=V1+A2$

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

Для остальных клеток Робот в обычной ситуации может попасть либо слева, либо сверху. Поэтому в ячейку $W2$ запишем: $=B2+МАКС(W1;V2)$

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

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

$V1=107$,
$W1=107+54=161$,
$V2=107+49=156$,
$W2=62+\max(161;156)=223$.

Теперь необходимо учесть внутренние стены.

В строках с $4$ по $15$ Робот не может попасть в клетки столбца $G$ слева из столбца $F$. Значит, в эти клетки можно прийти только сверху.

Столбцу $G$ исходной таблицы соответствует столбец $AB$ расчётной таблицы.

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

$=G4+AB3$

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

Стена между $S$ и $T$

В строках со $2$ по $10$ Робот не может попасть в столбец $T$ из столбца $S$. Следовательно, в клетки $T2:T10$ можно попасть только сверху.

Столбцу $T$ соответствует столбец $AO$ расчётной таблицы.

В ячейку $AO2$ запишем:

$=T2+AO1$

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

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

Этим клеткам соответствует диапазон $AG18:AL18$ расчётной таблицы.

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

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

После выполнения расчётов в правой нижней ячейке $AO20$ получим максимальную сумму: $2766$.

Для минимальной суммы используем ту же расчётную таблицу.

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

В ячейку $W2$ запишем: $=B2+МИН(W1;V2)$

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

После этого снова восстановим специальные формулы около стен:

  • в диапазоне $AB4:AB15$: $=G4+AB3$
  • в диапазоне $AO2:AO10$: $=T2+AO1$
  • в диапазоне $AG18:AL18$: $=L18+AF18$

Для первых клеток: $W2=62+\min(161;156)=218$.

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

Код на Python

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

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

N = len(s)

INF = 10 ** 9

mn = [[INF] * N for _ in range(N)]
mx = [[-INF] * N for _ in range(N)]

mn[0][0] = mx[0][0] = s[0][0]

# В эти клетки нельзя войти слева:
# G4:G15 и T2:T10
blocked_left = (
    {(i, 6) for i in range(3, 15)}
    | {(i, 19) for i in range(1, 10)}
)

# В эти клетки нельзя войти сверху:
# L18:Q18
blocked_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

        mn_prev = []
        mx_prev = []

        if j > 0 and (i, j) not in blocked_left:
            mn_prev.append(mn[i][j - 1])
            mx_prev.append(mx[i][j - 1])

        if i > 0 and (i, j) not in blocked_top:
            mn_prev.append(mn[i - 1][j])
            mx_prev.append(mx[i - 1][j])

        if mn_prev:
            mn[i][j] = s[i][j] + min(mn_prev)
            mx[i][j] = s[i][j] + max(mx_prev)

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

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

$2766$ $1820$

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

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