Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя.
Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной.
На поле может быть несколько финальных клеток.
В начальный момент робот обладает запасом энергии, которая расходуется на движение по клеткам. Расход энергии на прохождение каждой клетки, включая стартовую и финальную, равен числу, записанному в этой клетке.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
В обоих заданиях энергии должно хватить и на прохождение финальной клетки.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на
Ответ:
Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.
В ячейку B23 напишем значении =B2.
Для каждой ячейки левого столбца это будет сумма энергии текущей ячейки и ячейки сверху от текущей. Внесем
Для каждой ячейки строки это будет сумма энергии текущей ячейки и ячейки слева от текущей. Внесем
Далее в ячейку C24 вставим формулу =C3+МИН(C23;B24) и скопируем за маркер в ячейки C24:U42.
В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо большее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
В результате получим следующую таблицу:
| 50 | 93 | 143 | 185 | 228 | 289 | 379 | 416 | 474 | 502 | 573 | 598 | 642 | 725 | 813 | 853 | 929 | 986 | 1042 | 1141 |
| 109 | 188 | 157 | 10000 | 251 | 337 | 428 | 504 | 571 | 504 | 548 | 589 | 656 | 678 | 713 | 740 | 798 | 813 | 851 | 943 |
| 162 | 188 | 203 | 10000 | 268 | 291 | 376 | 423 | 505 | 535 | 602 | 633 | 715 | 720 | 792 | 769 | 771 | 790 | 853 | 886 |
| 164 | 196 | 263 | 10000 | 306 | 335 | 356 | 370 | 456 | 554 | 650 | 648 | 733 | 775 | 796 | 786 | 802 | 797 | 807 | 855 |
| 211 | 278 | 324 | 10000 | 347 | 383 | 360 | 429 | 462 | 540 | 562 | 10000 | 734 | 821 | 811 | 832 | 888 | 804 | 851 | 888 |
| 280 | 10000 | 10000 | 10000 | 399 | 386 | 420 | 490 | 498 | 562 | 623 | 10000 | 829 | 860 | 841 | 850 | 859 | 863 | 914 | 956 |
| 350 | 24 | 493 | 10000 | 460 | 422 | 479 | 569 | 578 | 613 | 623 | 10000 | 843 | 863 | 938 | 933 | 903 | 918 | 970 | 984 |
| 415 | 428 | 431 | 10000 | 480 | 516 | 527 | 589 | 604 | 663 | 653 | 10000 | 865 | 943 | 951 | 1026 | 925 | 1005 | 1044 | 997 |
| 435 | 481 | 456 | 10000 | 530 | 614 | 600 | 596 | 646 | 10000 | 10000 | 10000 | 943 | 1027 | 986 | 1027 | 977 | 1014 | 1034 | 1046 |
| 498 | 534 | 472 | 10000 | 533 | 617 | 688 | 643 | 670 | 694 | 762 | 10000 | 949 | 953 | 1011 | 1100 | 1034 | 1054 | 1070 | 1119 |
| 557 | 626 | 562 | 567 | 577 | 585 | 629 | 676 | 704 | 753 | 807 | 10000 | 1038 | 1025 | 1100 | 1165 | 1098 | 10000 | 1074 | 1154 |
| 583 | 591 | 596 | 656 | 639 | 613 | 641 | 723 | 766 | 845 | 813 | 10000 | 1128 | 1042 | 1137 | 1235 | 1112 | 10000 | 1161 | 1174 |
| 643 | 653 | 597 | 664 | 670 | 634 | 645 | 10000 | 801 | 839 | 909 | 10000 | 1216 | 1082 | 1107 | 1157 | 1186 | 10000 | 1217 | 1262 |
| 650 | 669 | 632 | 690 | 690 | 667 | 731 | 10000 | 853 | 924 | 940 | 979 | 982 | 1059 | 1072 | 10000 | 10000 | 10000 | 1312 | 1345 |
| 749 | 689 | 720 | 729 | 713 | 734 | 773 | 10000 | 908 | 943 | 960 | 985 | 1023 | 1086 | 1073 | 1115 | 1167 | 10000 | 1389 | 1357 |
| 788 | 710 | 797 | 789 | 784 | 10000 | 10000 | 10000 | 944 | 1014 | 1008 | 997 | 1061 | 1129 | 1095 | 1143 | 1168 | 10000 | 1400 | 1403 |
| 790 | 769 | 851 | 833 | 797 | 811 | 838 | 10000 | 1018 | 1090 | 1085 | 1034 | 1117 | 1147 | 1127 | 1206 | 1188 | 10000 | 1417 | 1454 |
| 865 | 786 | 805 | 806 | 823 | 899 | 852 | 10000 | 1105 | 1151 | 1129 | 1124 | 117 | 1179 | 1215 | 1208 | 33 | 1312 | 1383 | 1442 |
| 869 | 860 | 883 | 831 | 886 | 928 | 877 | 10000 | 1140 | 1149 | 53 | 95 | 1179 | 1276 | 1313 | 245 | 293 | 336 | 1377 | 1406 |
| 902 | 943 | 953 | 891 | 925 | 949 | 921 | 1020 | 1036 | 1113 | 1184 | 1246 | 1204 | 1266 | 1287 | 1277 | 1341 | 1358 | 1442 | 1481 |
Финальными клетками для робота могут быть ячейки: D27, H37, L30, R35 и U42.
Определим минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки. Для этого введем формулу:=МИН(D27;H37;L30;R35;U42). Значение минимального начального запаса энергии, который позволит роботу добраться до какой-нибудь финальной клетки — 324.
Определим минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Для этого введем формулу:=МАКС(D27;H37;L30;R35;U42). Значение минимального начального запаса энергии, который позволит роботу добраться до любой финальной клетки, — 1481.
Ответ: 324&1481.

