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

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

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

За­да­ние 18

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

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

1884
10113
13122
2356

 

Для ука­зан­ных вход­ных дан­ных от­ве­том долж­на быть пара чисел 38 и 22.

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

Ре­ше­ние.

Сна­ча­ла найдём мак­си­маль­ную де­неж­ную сумму. Для этого найдём мак­си­маль­ную де­неж­ную сумму для каж­дой ячей­ки таб­ли­цы. Для каж­дой ячей­ки верх­ней стро­ки это будет сумма всех ячеек слева от те­ку­щей. Для каж­дой ячей­ки ле­во­го столб­ца это будет сумма всех ячеек свер­ху от те­ку­щей. В ячей­ку A22 за­пи­шем фор­му­лу =СУММ($A$1:A1). Ско­пи­ру­ем эту фор­му­лу во все ячей­ки в диа­па­зо­не B22:T22 и в диа­па­зо­не A23:A41. Для ячеек C23:C29, E26:E34, G31:G39, J23:J30, M27:M35, P30:P39, по­сколь­ку слева от них име­ет­ся внут­рен­няя стен­ка, мак­си­маль­ная де­неж­ная сумма вы­чис­ля­ет­ся как сумма те­ку­щей ячей­ки и суммы свер­ху. Для ячеек D24:H24, I39:N39, по­сколь­ку свер­ху от них име­ет­ся внут­рен­няя стен­ка, мак­си­маль­ная де­неж­ная сумма вы­чис­ля­ет­ся как сумма те­ку­щей ячей­ки и суммы слева. Для осталь­ных ячеек будем срав­ни­вать зна­че­ние ячей­ки слева и зна­че­ние ячей­ки свер­ху и при­сва­и­вать те­ку­щей ячей­ке зна­че­ние суммы той ячей­ки, в ко­то­рой зна­че­ние боль­ше, и те­ку­щей ячей­ки. В B23 за­пи­шем фор­му­лу =МАКС(A23+B2;B22+B2) и ско­пи­ру­ем эту фор­му­лу во все остав­ши­е­ся ячей­ки диа­па­зо­на B23:T41. Таким об­ра­зом, в ячей­ке T41 по­лу­чим зна­че­ние мак­си­маль­ной де­неж­ной суммы  — 1099.

Ана­ло­гич­ным об­ра­зом найдём зна­че­ние ми­ни­маль­ной де­неж­ной суммы. Ячей­ки с внут­рен­ни­ми стен­ка­ми слева или свер­ху за­пол­ня­ют­ся также, как при по­ис­ке мак­си­маль­ной де­неж­ной суммы. В B23 за­пи­шем фор­му­лу =МИН(A23+B2;B22+B2) и ско­пи­ру­ем эту фор­му­лу во все остав­ши­е­ся ячей­ки диа­па­зо­на B23:T41. Таким об­ра­зом, в ячей­ке T41 по­лу­чим зна­че­ние ми­ни­маль­ной де­неж­ной суммы  — 1026.

 

Ответ: 10991026.


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

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ−2023 по ин­фор­ма­ти­ке