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

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

За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во или на одну клет­ку вниз. Клет­ка, из ко­то­рой робот не может сде­лать до­пу­сти­мо­го хода (спра­ва и снизу на­хо­дят­ся гра­ни­цы поля или за­прещённые клет­ки), на­зы­ва­ет­ся фи­наль­ной. На поле может быть не­сколь­ко фи­наль­ных кле­ток.

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

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

За­да­ние 18

За­да­ние 1. Опре­де­ли­те ми­ни­маль­ный на­чаль­ный запас энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до любой фи­наль­ной клет­ки.

За­да­ние 2. Опре­де­ли­те ко­ли­че­ство фи­наль­ных кле­ток, до ко­то­рых робот может дойти с на­чаль­ным за­па­сом энер­гии 2000 еди­ниц.

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. В от­ве­те за­пи­ши­те два числа: сна­ча­ла ответ на за­да­ние 1, затем ответ на за­да­ние 2.

 

Ответ:

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

Ре­ше­ние.

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

В ячей­ку B42 на­пи­шем зна­че­нии =B21.

Для каж­дой ячей­ки ле­во­го столб­ца это будет сумма энер­гии верх­ней ячей­ки и зна­че­нии из двух ячеек: те­ку­щей и вер­ней. Вне­сем в ячей­ку B24 фор­му­лу =B23+B3+B2 и ско­пи­ру­ем за мар­кер вниз до ячей­ки B42.

Для каж­дой ячей­ки стро­ки это будет сумма энер­гии преды­ду­щей ячей­ки и зна­че­ния из двух ячеек: те­ку­щей и левой. Вне­сем в ячей­ку С23 фор­му­лу =B23+C2+B2 и ско­пи­ру­ем за мар­кер впра­во до ячей­ки U23.

Далее в ячей­ку C24 вста­вим фор­му­лу =МИН(C23+C3+C2;B24+B3+C3) и ско­пи­ру­ем за мар­кер в ячей­ки C24:U42.

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

В ре­зуль­та­те по­лу­чим сле­ду­ю­щую таб­ли­цу:

Фи­наль­ны­ми клет­ка­ми для ро­бо­та могут быть ячей­ки: D27, H37, L30, R35, U42.

Опре­де­ли­те ми­ни­маль­ный на­чаль­ный запас энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до какой-⁠ни­будь фи­наль­ной клет­ки. Для этого вве­дем фор­му­лу:=МАКС(D27;H37;L30;R35;U42). Зна­че­ние ми­ни­маль­но­го на­чаль­но­го за­па­са энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до любой фи­наль­ной клет­ки,  — 2449.

Опре­де­лим ко­ли­че­ство фи­наль­ных кле­ток, до ко­то­рых робот может дойти с на­чаль­ным за­па­сом энер­гии 2000 еди­ниц. Из фи­наль­ных ячеек D27, H37, L30, R35, U42 толь­ко 3 ячей­ки (D27, H37, L30) имеют зна­че­ние мень­ше 2000. Ко­ли­че­ство фи­наль­ных кле­ток, до ко­то­рых робот может дойти с на­чаль­ным за­па­сом энер­гии 2000 еди­ниц,  — 3.

 

Ответ: 2449&3.


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