Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо и вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.
Пример входных данных:
1
8
8
4
10
1
1
3
1
3
12
2
2
3
5
6
Для данных из примера ответ 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.
В первую очередь отформатируем таблицу таким образом, чтобы с ней было удобнее работать. Для этого клетки, в которые можно прийти только слева, покрасим в желтый цвет, клетки, в которые можно прийти только сверху, — в зеленый.
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) заменим все вхождения МАКС в формулы на МИН.
PDF-версии: 