Задания
Версия для печати и копирования в MS Word
Тип 18 № 46976
i

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

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

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. Гра­ни­цы от­ме­че­ны утолщёнными ли­ни­я­ми.

За­да­ние 18

При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

 

1386950
30355717
32905532
44128043

 

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние по­лу­ча­ет­ся при дви­же­нии по марш­ру­ту:

3000 − 13 − 8 + 35 − 57 − 17 − 32 − 43 = 2865,

а ми­ни­маль­ное  — при дви­же­нии по марш­ру­ту:

3000 − 13 − 30 − 32 − 90 − 12 − 80 − 43 = 2700.

Ответ:

Спрятать решение

Ре­ше­ние.

Сна­ча­ла найдём мак­си­маль­но воз­мож­ный запас энер­гии. По­сколь­ку робот не может за­хо­дить в ячей­ки, окружённые сте­на­ми, уста­но­вим в ячей­ки E6, E11, K6, K11 зна­че­ния 10000. В ячей­ках с за­ряд­ны­ми стан­ци­я­ми ин­вер­ти­ру­ем по­ло­жи­тель­ные зна­че­ния в от­ри­ца­тель­ные, чтобы при ис­поль­зо­ва­нии вы­чи­та­ний зна­че­ния в за­ряд­ных стан­ци­ях, на­о­бо­рот, при­бав­ля­лись к за­па­су топ­ли­ва.

В ячей­ку A17 за­пи­шем фор­му­лу =3000-A1. Для диа­па­зо­нов B17:O17 и A18:A31, при пе­ре­хо­де в оче­ред­ную ячей­ку диа­па­зо­на, из те­ку­ще­го за­па­са энер­гии будем вы­чи­тать зна­че­ние этой ячей­ки. В ячей­ку B17 за­пи­шем фор­му­лу =A17-B1 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на C17:O17. В ячей­ку A18 за­пи­шем фор­му­лу =A17-A2 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на A18:A31. В ячей­ку B18 за­пи­шем фор­му­лу =МАКС(A18-B2;B17-B2) и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на B18:O31. Таким об­ра­зом, в ячей­ке O31 по­лу­чим мак­си­маль­но воз­мож­ное зна­че­ние за­па­са энер­гии  — 2093.

Те­перь найдём ми­ни­маль­но воз­мож­ный запас энер­гии. По­сколь­ку робот не может за­хо­дить в ячей­ки, окружённые сте­на­ми, уста­но­вим в ячей­ки E6, E11, K6, K11 зна­че­ния −10000. В ячей­ках с за­ряд­ны­ми стан­ци­я­ми ин­вер­ти­ру­ем по­ло­жи­тель­ные зна­че­ния в от­ри­ца­тель­ные, чтобы при ис­поль­зо­ва­нии вы­чи­та­ний зна­че­ния в за­ряд­ных стан­ци­ях, на­о­бо­рот, при­бав­ля­лись к за­па­су топ­ли­ва.

В ячей­ку A17 за­пи­шем фор­му­лу =3000-A1. Для диа­па­зо­нов B17:O17 и A18:A31, при пе­ре­хо­де в оче­ред­ную ячей­ку диа­па­зо­на, из те­ку­ще­го за­па­са энер­гии будем вы­чи­тать зна­че­ние этой ячей­ки. В ячей­ку B17 за­пи­шем фор­му­лу =A17-B1 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на C17:O17. В ячей­ку A18 за­пи­шем фор­му­лу =A17-A2 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на A18:A31. В ячей­ку B18 за­пи­шем фор­му­лу =МИН(A18-B2;B17-B2) и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на B18:O31. Таким об­ра­зом, в ячей­ке O31 по­лу­чим ми­ни­маль­но воз­мож­ное зна­че­ние за­па­са энер­гии  — 935.

 

Ответ: 2093 и 935.


Аналоги к заданию № 46976: 47015 Все

Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026