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

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

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

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

За­да­ние 18

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

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

В обоих за­да­ни­ях энер­гии долж­но хва­тить и на про­хож­де­ние фи­наль­ной клет­ки.

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

 

Ответ:

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

Ре­ше­ние.

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

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

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

Для каж­дой ячей­ки стро­ки это будет сумма энер­гии те­ку­щей ячей­ки и ячей­ки слева от те­ку­щей. Вне­сем в ячей­ку С42 фор­му­лу =B42+C21 и ско­пи­ру­ем за мар­кер впра­во до ячей­ки U42.

Далее в ячей­ку C41 вста­вим фор­му­лу =C20+МИН(C42;B41) и ско­пи­ру­ем за мар­кер в ячей­ки C42:U23.

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

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

 

9029369089507698309208539118719429539971080114011191195120312401339
852893858100007267958438169078438879289951017105210791137114611841276
7937988441000070370975272881084190894710291071114311101112113111921210
74077283910000686686667681767865888903988104310641081111211191129177
738820881100006486426467157488267921000012561293123112771296127613231360
6911000010000100006075946547247267847701000012551206121612341210126913321337
62256848610000555591650686690720709100001160116711861265120112561309269
55249441710000494588636596616696991000011461147108911821157124412531
4874814141000047457159453458410000100001000011241067107611171135116011791228
46742838910000424473521527541565633100001046983104111261083112311591232
404375373377421389433480514573627100001040979100810371026100001333343
345283283372394381392474536628634100009590791997296210000132926
31927524931633235336410000842878852100008618908248749481000012421243
2592132483063013344201000080784756770773850799100001000010000118615
252194282291281348390100007557557257317728357868288801000010911072
1531742612522581000010000100007007207057067707997858338581000010141060
114173229192187201228100006646465769757376384285610000100305
112128147148174262276100005905758067667078979183691598604
37111189214277319344100005035125366076170880684390394698701
33116186246285309353452468545616678703765786818882904988106

 

Фи­наль­ны­ми клет­ка­ми для ро­бо­та могут быть ячей­ки: D29, H39, L32, R37 и U23.

Опре­де­лим ми­ни­маль­ный на­чаль­ный запас энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до какой-ни­будь фи­наль­ной клет­ки. Для этого вве­дем фор­му­лу:=МИН(D29;H39;L32;R37;U23). Зна­че­ние ми­ни­маль­но­го на­чаль­но­го за­па­са энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до какой-⁠ни­будь фи­наль­ной клет­ки,  — 228.

Опре­де­лим ми­ни­маль­ный на­чаль­ный запас энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до любой фи­наль­ной клет­ки. Для этого вве­дем фор­му­лу:=МАКС(D29;H39;L32;R37;U23). Зна­че­ние ми­ни­маль­но­го на­чаль­но­го за­па­са энер­гии, ко­то­рый поз­во­лит ро­бо­ту до­брать­ся до любой фи­наль­ной клет­ки,  — 1339.

 

Ответ: 228&1339.


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