Задание №18 ЕГЭ Информатика с ответом и решением
Ответ: 1204502
Условие
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
| 1 | 8 | 8 | 4 |
|---|---|---|---|
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел 41 и 22.
Подсказки — как подойти к решению
- Данные — таблица N×N в файле: её удобно прочитать программно, разбивая каждую строку на числа (посмотри, чем разделены ячейки — пробелом или точкой с запятой).
- Робот ходит только вправо и вниз, поэтому сумму по маршруту считают динамикой: в каждую клетку приходит лучшая сумма из верхнего или из левого соседа, к ней прибавляется монета самой клетки.
- Первую строку и первый столбец заполняй накоплением — попасть туда можно единственным способом; таблицу посчитай дважды (с выбором максимума и минимума). В ответ сначала идёт максимальная сумма, затем минимальная, записанные подряд без разделителей.
Решение
Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек слева от текущей. Для каждой ячейки левого столбца это будет сумма всех ячеек сверху от текущей. В ячейку L1 запишем формулу =СУММ($A$1:A1). Скопируем эту формулу во все ячейки в диапазоне M1:U1 и в диапазоне L2:L10. Для остальных ячеек будем сравнивать значение ячейки слева и значение ячейки сверху и присваивать текущей ячейке значение суммы той ячейки, в которой значение больше, и текущей ячейки. В M2 запишем формулу =ЕСЛИ(L2>M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10. Таким образом, в ячейке U10 получим значение максимальной денежной суммы — 1204.
Аналогичным образом найдём значение минимальной денежной суммы. Ячейки диапазонов L1:L10 и M1:U1 заполняются также, как при поиске максимальной денежной суммы. В M2 запишем формулу =ЕСЛИ(L2 < M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10. Таким образом, в ячейке U10 получим значение минимальной денежной суммы — 502.
Ответ: 1204502.
Приведём решение Артёма Гридина на языке Python.
s = tuple(tuple(int(x) for x in m.split(';')) for m in open('18_demo.csv').read().splitlines())
N = len(s)
for f in [lambda a, b: max(a, b), lambda a,b: min(a, b)]:
m = [[0 for _ in range(N)] for _ in range(N)]
m[0][0] = s[0][0]
for i in range(1, N):
m[0][i]=s[0][i]+m[0][i-1]
m[i][0]=s[i][0]+m[i-1][0]
for row in range(1, N):
for column in range(1, N):
m[row][column] = s[row][column]+f(m[row-1][column], m[row][column-1])
print(m[N-1][N-1],end='')
·
Приведём решение Дмитрия Пучикова на языке Python.
mp = []
width = 0
height = 0
with open('18_demo.csv') as fil:
for line in fil:
mp.append([int(i) for i in line.split(' ')])
if (width == 0):
width = len(mp[len(mp) - 1])
height = len(mp)
minVal = 999999999
maxVal = 0
candidates = [{
"x":0,
"y":0,
"val":mp[0][0]
}]
while len(candidates) > 0:
curCand = candidates.pop(0)
if (curCand["x"] + 1 < width):
candidates.append({
"x":curCand["x"] + 1,
"y":curCand["y"],
"val":curCand["val"] + mp[curCand["x"] + 1][curCand["y"]]
})
if (curCand["y"] + 1 < height):
candidates.append({
"x":curCand["x"],
"y":curCand["y"] + 1,
"val":curCand["val"] + mp[curCand["x"]][curCand["y"] + 1]
})
if ((curCand["x"] == 9) and (curCand["y"] == 9)):
if (maxVal < curCand["val"]):
maxVal = curCand["val"]
elif (minVal > curCand["val"]):
minVal = curCand["val"]
print(maxVal, minVal)
·
Типичные ошибки
- Числа склеены в обратном порядке: сначала должна стоять максимальная сумма, затем минимальная.
- Две суммы сложены. По условию их нужно записать друг за другом без разделительных знаков, а не складывать.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №18 по информатике