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

ЕГЭ, Информатика: 18. Исполнитель Робот: все задания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для первых клеток:

$V1=25$,
$W1=25+25=50$,
$V2=25+20=45$,
$W2=24+\max(50;45)=74$.

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

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

Для первых клеток: $W2=24+\min(50;45)=69$.

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

Код на Python

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

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

N = len(s)

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

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

for j in range(1, N):
    mn[0][j] = mn[0][j - 1] + s[0][j]
    mx[0][j] = mx[0][j - 1] + s[0][j]

for i in range(1, N):
    mn[i][0] = mn[i - 1][0] + s[i][0]
    mx[i][0] = mx[i - 1][0] + s[i][0]

for i in range(1, N):
    for j in range(1, N):
        mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
        mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])

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

Программа выводит: $918$ $825$.

Показать
Очки опыта 20
Спросить Зави
22. Задание #297242
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

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

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

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

В ячейку $W1$: $=V1+B1$ и скопируем вправо до $AO1$.

В ячейку $V2$: $=V1+A2$ и скопируем вниз до $V20$.

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

Для первых клеток:

$V1=106$,
$W1=106+7=113$,
$V2=106+22=128$,
$W2=60+\max(113;128)=188$.

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

Из-за стены справа от $F4:F15$ в клетки $G4:G15$ можно попасть только сверху. В расчётной таблице это диапазон $AB4:AB15$.

В $AB4$ запишем: $=G4+AB3$ и скопируем до $AB15$.

Из-за стены справа от $S2:S10$ в клетки $T2:T10$ также можно попасть только сверху. В расчётной таблице это диапазон $AO2:AO10$.

В $AO2$ запишем: $=T2+AO1$ и скопируем до $AO10$.

Через стену снизу от $L17:Q17$ нельзя пройти вниз, поэтому в клетки $L18:Q18$ можно попасть только слева.

В $AG18$ запишем: $=L18+AF18$ и скопируем вправо до $AL18$.

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

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

Для первых клеток: $W2=60+\min(113;128)=173$.

Формулы около стен остаются такими же: $AB4=G4+AB3$, $AO2=T2+AO1$, $AG18=L18+AF18$.

После копирования формул в ячейке $AO20$ получим минимальную сумму: $1059$.

Код на Python

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

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-22.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]

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

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

        mn[i][j] = s[i][j] + min(a)
        mx[i][j] = s[i][j] + max(b)

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

Программа выводит: $2391$ $1059$.

Показать
Очки опыта 20
Спросить Зави
23. Задание #297249
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

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

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

В ячейку $W1$: $=V1+B1$ и скопируем вправо до $AO1$.

В ячейку $V2$: $=V1+A2$ и скопируем вниз до $V20$.

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

Для первых клеток:

$V1=24$,
$W1=24+25=49$,
$V2=24+20=44$,
$W2=20+\max(49;44)=69$.

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

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

Для первых клеток: $W2=20+\min(49;44)=64$.

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

Код на Python

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

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

N = len(s)

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

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

for j in range(1, N):
    mn[0][j] = mn[0][j - 1] + s[0][j]
    mx[0][j] = mx[0][j - 1] + s[0][j]

for i in range(1, N):
    mn[i][0] = mn[i - 1][0] + s[i][0]
    mx[i][0] = mx[i - 1][0] + s[i][0]

for i in range(1, N):
    for j in range(1, N):
        mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
        mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])

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

Программа выводит: $913$ $819$.

Показать
Очки опыта 20
Спросить Зави
24. Задание #297246
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

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

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

В ячейку $R1$: $=Q1+B1$ и скопируем вправо до $AE1$.

В ячейку $Q2$: $=Q1+A2$ и скопируем вниз до $Q15$.

Для поиска минимальной суммы в $R2$ запишем: $=B2+МИН(R1;Q2)$ и скопируем формулу в диапазон $R2:AE15$.

Для первых клеток:

$Q1=22$,
$R1=22+21=43$,
$Q2=22+28=50$,
$R2=11+\min(43;50)=54$.

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

Для поиска максимальной суммы заменим функцию МИН на МАКС: $=B2+МАКС(R1;Q2)$ и скопируем формулу в диапазон $R2:AE15$.

Для первых клеток: $R2=11+\max(43;50)=61$.

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

Код на Python

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

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

N = len(s)

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

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

for j in range(1, N):
    mn[0][j] = mn[0][j - 1] + s[0][j]
    mx[0][j] = mx[0][j - 1] + s[0][j]

for i in range(1, N):
    mn[i][0] = mn[i - 1][0] + s[i][0]
    mx[i][0] = mx[i - 1][0] + s[i][0]

for i in range(1, N):
    for j in range(1, N):
        mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
        mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])

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

Программа выводит: $438$ $669$.

Показать
Очки опыта 20
Спросить Зави
25. Задание #297243
Решено верно
Решено неверно
Сообщить о проблеме

Квадрат разлинован на $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=99$,
$W1=99+72=171$,
$V2=99+83=182$,
$W2=78+\max(171;182)=260$.

Около стен оставляем только разрешённое направление движения. Например, справа от стены $B3:B6$ в клетки $C3:C6$ можно попасть только сверху, поэтому в $X3$ запишем: $=C3+X2$ и скопируем до $X6$.

Под стеной $F2:I2$ в клетки $F3:I3$ можно попасть только слева. В $AA3$ запишем: $=F3+Z3$ и скопируем вправо до $AD3$.

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

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

Максимальные суммы в них:

$AF14=1804$,
$AN14=2144$,
$AL20=2468$,
$AO20=2287$.

Следовательно, $\max(1804;2144;2468;2287)=2468$.

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

Для первых клеток: $W2=78+\min(171;182)=249$.

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

Минимальные суммы в конечных клетках: $AF14=938$, $AN14=1116$, $AL20=1297$, $AO20=1281$.

Следовательно, $\min(938;1116;1297;1281)=938$.

Код на Python

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

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-25.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 == 0 and j == 0:
            continue

        a, b = [], []

        if j > 0 and (i, j - 1) not in right:
            if mn[i][j - 1] < 10 ** 9:
                a.append(mn[i][j - 1])
                b.append(mx[i][j - 1])

        if i > 0 and (i - 1, j) not in down:
            if mn[i - 1][j] < 10 ** 9:
                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 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))

Программа выводит: $2468$ $938$.

Показать
Очки опыта 20
Спросить Зави
26. Задание #297260
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Вертикальные стены расположены справа от $D3:D4$, $G3:G17$, $L5:L7$, $L15:L18$, $R12:R16$, $S3:S5$. Горизонтальные стены расположены снизу от $B4:D4$, $P5:S5$, $J7:L7$, $N16:R16$, $D17:G17$, $I18:L18$.

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

В $V1$ запишем: $=A1$

В $W1$: $=V1+B1$ и скопируем вправо до $AO1$.

В $V2$: $=V1+A2$ и скопируем вниз до $V20$.

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

Для первых клеток:

$V1=24$,
$W1=24+22=46$,
$V2=24+12=36$,
$W2=60+\max(46;36)=106$.

Около стен оставляем только разрешённое направление движения. Например, справа от стены $D3:D4$ в клетки $E3:E4$ можно попасть только сверху, поэтому в $Z3$ запишем: $=E3+Z2$ и скопируем до $Z4$.

Справа от стены $G3:G17$ для диапазона $H3:H17$ используем формулу вида: $=H3+AC2$ и копируем вниз.

Под стеной $B4:D4$ в клетки $B5:D5$ можно попасть только слева. В $W5$ запишем: $=B5+V5$ и скопируем вправо до $Y5$.

Аналогично учитываем остальные стены.

Конечными клетками являются $D4$, $S5$, $L7$, $R16$, $G17$, $L18$ и $T20$.

Максимальные суммы в них равны соответственно: $380$, $1366$, $1156$, $1925$, $1254$, $1670$, $2383$.

Следовательно, $\max(380;1366;1156;1925;1254;1670;2383)=2383$.

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

Для первых клеток: $W2=60+\min(46;36)=96$.

Формулы около стен остаются такими же.

Минимальные суммы в конечных клетках: $240$, $790$, $735$, $1003$, $664$, $1075$, $1376$.

Следовательно, $\min(240;790;735;1003;664;1075;1376)=240$.

Код на Python

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

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

N = len(s)

right = set()

for r1, r2, c in [
    (3, 4, 4), (3, 17, 7),
    (5, 7, 12), (15, 18, 12),
    (12, 16, 18), (3, 5, 19)
]:
    for r in range(r1 - 1, r2):
        right.add((r, c - 1))

down = set()

for r, c1, c2 in [
    (4, 2, 4), (5, 16, 19),
    (7, 10, 12), (16, 14, 18),
    (17, 4, 7), (18, 9, 12)
]:
    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))

Программа выводит: $2383$ $240$.

Показать
Очки опыта 20
Спросить Зави
27. Задание #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$.

Код на 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
Спросить Зави
28. Задание #297267
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

В исходном файле таблица занимает диапазон $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=101$,
$W1=101+34=135$,
$V2=101+48=149$,
$W2=58+\max(135;149)=207$.

Теперь учтём стены. Из-за стены справа от $F4:F15$ в клетки $G4:G15$ можно попасть только сверху. В расчётной таблице это диапазон $AB4:AB15$.

В $AB4$ запишем: $=G4+AB3$ и скопируем до $AB15$.

Через стену снизу от $L17:Q17$ нельзя пройти вниз, поэтому в клетки $L18:Q18$ можно попасть только слева.

В $AG18$ запишем: $=L18+AF18$ и скопируем вправо до $AL18$.

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

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

Для первых клеток: $W2=58+\min(135;149)=193$.

Формулы около стен остаются такими же: $AB4=G4+AB3$, $AG18=L18+AF18$.

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

Код на Python

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

s = tuple(
    tuple(map(int, row.split(';')))
    for row in open('18-28.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])

        mn[i][j] = s[i][j] + min(a)
        mx[i][j] = s[i][j] + max(b)

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

Программа выводит: $2691$ $1795$.

Показать
Очки опыта 20
Спросить Зави
29. Задание #297263
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Вертикальные стены расположены справа от $F13:F18$, $G3:G6$, $J11:J16$, $L3:L8$, $O16:O20$, $P13:P18$, $R3:R10$.

Горизонтальные стены расположены снизу от $C2:G2$, $F8:L8$, $G10:J10$, $N10:R10$, $C12:F12$, $Q12:S12$, $L15:O15$.

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

В $V1$ запишем: $=A1$

В $W1$: $=V1+B1$ и скопируем вправо до $AO1$.

В $V2$: $=V1+A2$ и скопируем вниз до $V20$.

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

Для первых клеток:

$V1=9$,
$W1=9+23=32$,
$V2=9+28=37$,
$W2=22+\max(32;37)=59$.

После этого учитываем стены. Например, справа от стены $L3:L8$ в клетки $M3:M8$ можно попасть только сверху, поэтому в $AH3$ запишем: $=M3+AH2$ и скопируем до $AH8$.

Под стеной $F8:L8$ в клетки $F9:L9$ можно попасть только слева. В $AA9$ запишем: $=F9+Z9$ и скопируем вправо до $AG9$.

Аналогично изменяем формулы около остальных стен.

Клетка $Q13$ закрыта стенами сверху и слева, поэтому попасть в неё нельзя. Из-за вертикальной стены диапазон $Q13:Q18$ также недостижим. Для поиска максимума в соответствующий диапазон $AL13:AL18$ запишем большое отрицательное значение, например $-10^9$.

Конечными клетками являются $L8$, $R10$, $O20$ и $T20$. Максимальные суммы в них равны: $1168$, $1680$, $2009$, $1908$.

Следовательно, $\max(1168;1680;2009;1908)=2009$.

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

Для первых клеток: $W2=22+\min(32;37)=54$.

В недостижимый диапазон $AL13:AL18$ запишем $10^9$. Формулы около стен остаются такими же.

Минимальные суммы в конечных клетках: $628$, $836$, $1090$, $1004$.

Следовательно, $\min(628;836;1090;1004)=628$.

Код на Python

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

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

N = len(s)

right = set()

for r1, r2, c in [
    (13, 18, 6), (3, 6, 7), (11, 16, 10),
    (3, 8, 12), (16, 20, 15),
    (13, 18, 16), (3, 10, 18)
]:
    for r in range(r1 - 1, r2):
        right.add((r, c - 1))

down = set()

for r, c1, c2 in [
    (2, 3, 7), (8, 6, 12), (10, 7, 10),
    (10, 14, 18), (12, 3, 6),
    (12, 17, 19), (15, 12, 15)
]:
    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:
            if mn[i][j - 1] < 10 ** 9:
                a.append(mn[i][j - 1])
                b.append(mx[i][j - 1])

        if i > 0 and (i - 1, j) not in down:
            if mn[i - 1][j] < 10 ** 9:
                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))

Программа выводит: $2009$ $628$.

Показать
Очки опыта 20
Спросить Зави
30. Задание #297269
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Вертикальные стены расположены справа от $D12:D16$, $G4:G19$, $L2:L11$, $Q11:Q18$, $S5:S10$.

Горизонтальные стены расположены снизу от $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+12=36$,
$V2=24+11=35$,
$W2=74+\max(36;35)=110$.

После этого учитываем стены. Например, справа от стены $L2:L11$ в клетки $M2:M11$ можно попасть только сверху, поэтому в $AH2$ запишем: $=M2+AH1$ и скопируем до $AH11$.

Справа от стены $G4:G19$ для клеток $H4:H19$ в $AC4$ запишем: $=H4+AC3$ и скопируем до $AC19$.

Под стеной $P4:S4$ в клетки $P5:S5$ можно попасть только слева. В $AK5$ запишем: $=P5+AJ5$ и скопируем вправо до $AN5$.

Аналогично изменяем формулы около остальных стен.

Конечными клетками являются $L11$, $D16$, $Q18$, $G19$ и $T20$.

Максимальные суммы в них: $1329$, $1198$, $2270$, $1488$, $2404$.

Следовательно, $\max(1329;1198;2270;1488;2404)=2404$.

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

Для первых клеток: $W2=74+\min(36;35)=109$.

Формулы около стен остаются такими же.

Минимальные суммы в конечных клетках: $695$, $481$, $1365$, $681$, $1410$.

Следовательно, $\min(695;481;1365;681;1410)=481$.

Код на Python

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

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

N = len(s)

right = set()

for r1, r2, c in [
    (12, 16, 4), (4, 19, 7), (2, 11, 12),
    (11, 18, 17), (5, 10, 19)
]:
    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))

Программа выводит: $2404$ $481$.

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

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