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

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

За­да­ние 18

 

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

 

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

1884
10113
13122
2356

Для дан­ных из при­ме­ра ответ 34 22.

 

Ответ:

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

Ре­ше­ние.

Сна­ча­ла найдём мак­си­маль­ную де­неж­ную сумму. Для этого найдём мак­си­маль­ную де­неж­ную сумму для каж­дой ячей­ки таб­ли­цы. Для каж­дой ячей­ки верх­ней стро­ки это будет сумма всех ячеек слева от те­ку­щей. Для каж­дой ячей­ки ле­во­го столб­ца это будет сумма всех ячеек свер­ху от те­ку­щей. В ячей­ку A22 за­пи­шем фор­му­лу =СУММ($A$1:A1). Ско­пи­ру­ем эту фор­му­лу во все ячей­ки в диа­па­зо­не B22:T22 и в диа­па­зо­не A23:A41.

Для ячеек С30:С34, E25:E38, Q29:Q33 и S24:S38, по­сколь­ку слева от них име­ет­ся внут­рен­няя стен­ка, мак­си­маль­ная де­неж­ная сумма вы­чис­ля­ет­ся как сумма те­ку­щей ячей­ки и суммы свер­ху, в ячей­ку C30 за­пи­шем фор­му­лу =C29+C9 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на С30:С34. Ана­ло­гич­но по­сту­па­ем для всех ячеек диа­па­зо­нов E25:E38, Q29:Q33 и S24:S38.

Для ячеек F24:J24, I27:M27, K30:O30, K33:O33, I36:M36 и F40:J40, по­сколь­ку свер­ху от них име­ет­ся внут­рен­няя стен­ка, мак­си­маль­ная де­неж­ная сумма вы­чис­ля­ет­ся как сумма те­ку­щей ячей­ки и суммы слева, в ячей­ку F24 за­пи­шем фор­му­лу =E24+F3 и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на F24:J24. Ана­ло­гич­но по­сту­па­ем для всех ячеек диа­па­зо­нов I27:M27, K30:O30, K33:O33, I36:M36 и F40:J40.

Для осталь­ных ячеек будем срав­ни­вать зна­че­ние ячей­ки слева и зна­че­ние ячей­ки свер­ху и при­сва­и­вать те­ку­щей ячей­ке зна­че­ние суммы той ячей­ки, в ко­то­рой зна­че­ние боль­ше, и те­ку­щей ячей­ки. В B23 за­пи­шем фор­му­лу =МАКС(A23+B2;B22+B2) и ско­пи­ру­ем эту фор­му­лу во все остав­ши­е­ся ячей­ки диа­па­зо­на B23:T41. Таким об­ра­зом, в ячей­ке T41 по­лу­чим зна­че­ние мак­си­маль­ной де­неж­ной суммы   — 1102.

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

 

Ответ: 1102  1029.

 

При­ведём ре­ше­ние Ев­ге­ния Дж­об­са (элек­трон­ные таб­ли­цы).

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

 

A B C D E F G H I J K L M N O P Q R S T
1 27 29 25 26 27 28 30 30 27 26 27 30 28 25 29 30 26 25 27 28
2 27 29 25 27 30 26 25 26 25 30 25 25 30 25 30 28 28 29 27 27
3 30 30 26 26 30 28 27 25 29 30 26 27 27 26 30 30 25 26 29 29
4 25 30 27 29 27 26 29 28 29 25 27 29 29 29 27 29 29 27 30 26
5 27 30 27 28 28 26 26 28 27 25 28 30 28 27 28 28 28 29 30 28
6 28 30 28 25 25 25 29 25 30 25 27 29 27 26 30 29 25 29 27 28
7 29 25 25 28 30 26 27 26 30 26 27 25 25 29 26 29 29 28 30 30
8 26 28 28 29 26 30 29 29 25 29 26 26 30 25 29 28 25 27 30 28
9 29 26 30 29 27 28 28 25 28 25 25 27 29 29 27 26 29 27 28 26
10 26 28 28 25 26 27 30 27 27 27 30 26 30 25 25 26 29 25 26 28
11 30 30 27 29 26 26 30 25 25 30 26 27 27 25 25 25 30 28 26 25
12 27 26 29 25 29 25 30 27 25 29 29 26 25 30 29 25 28 30 26 26
13 25 29 27 27 29 25 30 27 25 29 25 26 30 27 26 27 30 26 27 28
14 27 30 30 26 28 27 25 29 26 27 30 26 28 28 28 30 26 29 27 30
15 26 27 28 27 26 28 26 26 26 28 29 27 26 28 29 30 30 29 27 29
16 27 27 26 30 26 29 27 28 30 27 28 30 26 29 29 28 28 26 26 25
17 29 30 30 29 30 26 28 26 28 30 25 29 25 27 26 25 25 29 27 28
18 29 30 26 28 26 26 29 28 29 29 25 27 25 29 27 29 25 29 29 28
19 30 30 28 27 30 27 28 26 27 25 26 25 28 26 28 26 27 27 27 25
20 25 27 30 26 29 28 25 29 27 27 27 27 27 29 25 25 30 26 29 25

 

Про­из­во­дить рас­че­ты будем в диа­па­зо­не A22:T41. В ячей­ку A22 пе­ре­не­сем зна­че­ние из A1, на­при­мер, с по­мо­щью фор­му­лы =A1.

После чего в ячей­ке B23 на­пи­шем фор­му­лу для вы­бо­ра мак­си­маль­но­го счета в преды­ду­щих ячей­ках (свер­ху и слева) и до­бав­ле­ния к этому зна­че­нию со­от­вет­ству­ю­щей ячей­ки из на­чаль­но­го поля (B2) и за­пол­ним этой фор­му­лой весь диа­па­зон B23:T41. По­лу­ча­ем:

B23 =макс(B22;A23)+B2.

 

A B C D E F G H 1 J K L M N 0 P Q R 5 T
19 30 30 28 27 30 27 28 26 27 25 26 25 28 26 28 26 27 27 27 25
20 25 27 30 26 29 28 25 29 27 27 27 27 27 29 25 25 30 26 29 25
21
22 27
23 29 54 81 111 137 162 188 213 243 268 293 323 348 378 406 434 463 490 517
24 59 85 111 141 169 196 221 250 280 306 333 360 386 416 446 471 497 526 555
25 89 116 145 172 198 227 255 284 309 336 365 394 423 450 479 508 535 565 591
26 119 146 174 202 228 254 283 311 336 364 395 423 450 478 507 536 565 595 623
27 149 177 202 227 253 283 308 341 366 393 424 451 477 508 537 562 594 622 651
28 174 202 230 260 286 313 339 371 397 424 449 476 506 534 566 595 623 653 683
29 202 230 259 286 316 345 374 399 428 454 480 510 535 564 594 620 650 683 711
30 228 260 289 316 344 373 399 427 453 479 507 539 568 595 621 650 677 711 737
31 256 288 314 342 371 403 430 457 484 514 540 570 595 620 647 679 704 737 765
32 286 315 344 370 397 433 458 483 514 540 567 597 622 647 672 709 737 763 790
33 312 344 369 399 424 463 490 515 544 573 599 624 654 683 708 737 767 793 819
34 341 371 398 428 453 493 520 545 574 599 625 655 682 709 736 767 793 820 848
35 371 401 427 456 483 518 549 575 602 632 658 686 714 742 772 798 827 854 884
36 398 429 456 482 511 544 575 601 630 661 688 714 742 771 802 832 861 888 917
37 425 455 486 512 541 571 603 633 660 689 719 745 774 803 831 860 887 914 942
38 455 485 515 545 571 599 629 661 691 716 748 773 801 829 856 885 916 943 971
39 485 511 543 571 597 628 657 690 720 745 775 800 830 857 886 911 945 974 1002
40 515 543 570 601 628 656 683 717 745 771 800 828 856 885 912 939 972 1001 1027
41 542 573 599 630 658 683 712 744 772 799 827 855 885 910 937 969 998 1030 1055

 

Те­перь ско­пи­ру­ем фор­ма­ти­ро­ва­ние ис­ход­но­го поля (ПКМ-⁠Ко­пи­ро­вать или Ctrl + C) и вста­вим толь­ко фор­ма­ти­ро­ва­ние на за­пол­ня­е­мое поле и уда­лим все дан­ные в за­кра­шен­ных ячей­ках.

И за­пол­ним ячей­ки B22 и A23 со­от­вет­ству­ю­щи­ми для них фор­му­ла­ми (толь­ко дви­же­ние слева и толь­ко дви­же­ние спра­ва):

B22=A22+B1;

A23=A22+A2.

После чего ско­пи­ру­ем со­дер­жи­мое дан­ных ячеек и вста­вим в пу­стые ячей­ки с со­от­вет­ству­ю­щи­ми цве­та­ми.

Те­перь с по­мо­щью меню за­ме­ны (Ctrl + H) за­ме­ним все вхож­де­ния МАКС в фор­му­лы на МИН.


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

Источник: ЕГЭ по ин­фор­ма­ти­ке 06.04.2023. До­сроч­ная волна
Спрятать решение · Помощь


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