Максимальная и минимальная сумма

ЕГЭ · Информатика · Тапсырма 18 · Динамикалық бағдарламалау

ЖоғарыФИПИE60642Толық шешім≈ 10 минут

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

Файл тапсырмаға

E60642.zipАрхив ZIP · 33 КБВнутри: 2_18.xlsx, 2_18.ods, 2_18.xls

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

Условие как в банке ФИПИ — открыть и сверить

Дұрыс жауапты жазыңыз.

Тапсырма выполняется с использованием прилагаемых
файлов.

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

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

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

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

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

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Жауап

Это задание с развёрнутым решением: ответом считается шешімнің барысын жазу, жол емес. Шешімді қағазға жазып, салыстырыңыз с разбором — там каждый шаг с обоснованием.

Талдауды ашу

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, алдыңғысы оқылған кезде, — жауапқа бірден секіріп кетпеу үшін.

1Мягкая — с чего смотретьдеңгей 1 из 3

Для каждой клетки рассмотрите все допустимые пути, которыми Робот может в неё попасть.

2Жетекші — қандай сандарды есептеудеңгей 2 из 3

Храните для каждой клетки две величины: максимальную и минимальную сумму монет на пути из начальной клетки.

3Тікелей — іс жүзінде шешімдеңгей 3 из 3

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

Всё равно не складывается?Полное Шешім с обоснованием каждого шага — на отдельной странице.

Шешімді ашу

ПредыдущаяМаршрут Робота по клеткамСледующаяМинимальная и максимальная сумма

Тапсырма 18 ЕГЭ, информатика