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

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

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

На поле может быть не­сколь­ко фи­наль­ных кле­ток.

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

За­да­ние 18

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

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

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

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

 

Ответ:

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

Ре­ше­ние.

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

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

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

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

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

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

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

 

509314318522828937941647450257359864272581385392998610421141
10918815710000251337428504571504548589656678713740798813851943
16218820310000268291376423505535602633715720792769771790853886
16419626310000306335356370456554650648733775796786802797807855
2112783241000034738336042946254056210000734821811832888804851888
28010000100001000039938642049049856262310000829860841850859863914956
350244931000046042247956957861362310000843863938933903918970984
4154284311000048051652758960466365310000865943951102692510051044997
4354814561000053061460059664610000100001000094310279861027977101410341046
4985344721000053361768864367069476210000949953101111001034105410701119
55762656256757758562967670475380710000103810251100116510981000010741154
58359159665663961364172376684581310000112810421137123511121000011611174
6436535976646706346451000080183990910000121610821107115711861000012171262
650669632690690667731100008539249409799821059107210000100001000013121345
74968972072971373477310000908943960985102310861073111511671000013891357
78871079778978410000100001000094410141008997106111291095114311681000014001403
790769851833797811838100001018109010851034111711471127120611881000014171454
86578680580682389985210000110511511129112411711791215120833131213831442
8698608838318869288771000011401149539511791276131324529333613771406
9029439538919259499211020103611131184124612041266128712771341135814421481

 

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

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

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

 

Ответ: 324&1481.


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