Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя.
Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает запасом энергии, которая расходуется на движение по клеткам. Расход энергии на прохождение каждой клетки, включая стартовую и финальную, равен числу, записанному в этой клетке.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
В обоих заданиях энергии должно хватить и на прохождение финальной клетки.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на
Ответ:
Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.
В ячейку B42 напишем значении =B21.
Для каждой ячейки левого столбца это будет сумма энергии текущей ячейки и ячейки снизу от текущей. Внесем
Для каждой ячейки строки это будет сумма энергии текущей ячейки и ячейки слева от текущей. Внесем
Далее
В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо большее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
В результате получим следующую таблицу:
| 902 | 936 | 908 | 950 | 769 | 830 | 920 | 853 | 911 | 871 | 942 | 953 | 997 | 1080 | 1140 | 1119 | 1195 | 1203 | 1240 | 1339 |
| 852 | 893 | 858 | 10000 | 726 | 795 | 843 | 816 | 907 | 843 | 887 | 928 | 995 | 1017 | 1052 | 1079 | 1137 | 1146 | 1184 | 1276 |
| 793 | 798 | 844 | 10000 | 703 | 709 | 752 | 728 | 810 | 841 | 908 | 947 | 1029 | 1071 | 1143 | 1110 | 1112 | 1131 | 1192 | 1210 |
| 740 | 772 | 839 | 10000 | 686 | 686 | 667 | 681 | 767 | 865 | 888 | 903 | 988 | 1043 | 1064 | 1081 | 1112 | 1119 | 1129 | 177 |
| 738 | 820 | 881 | 10000 | 648 | 642 | 646 | 715 | 748 | 826 | 792 | 10000 | 1256 | 1293 | 1231 | 1277 | 1296 | 1276 | 1323 | 1360 |
| 691 | 10000 | 10000 | 10000 | 607 | 594 | 654 | 724 | 726 | 784 | 770 | 10000 | 1255 | 1206 | 1216 | 1234 | 1210 | 1269 | 1332 | 1337 |
| 622 | 568 | 486 | 10000 | 555 | 591 | 650 | 686 | 690 | 720 | 709 | 10000 | 1160 | 1167 | 1186 | 1265 | 1201 | 1256 | 1309 | 269 |
| 552 | 494 | 417 | 10000 | 494 | 588 | 636 | 596 | 61 | 669 | 699 | 10000 | 1146 | 1147 | 1089 | 1182 | 1157 | 1244 | 1253 | 1 |
| 487 | 481 | 414 | 10000 | 474 | 571 | 594 | 534 | 584 | 10000 | 10000 | 10000 | 1124 | 1067 | 1076 | 1117 | 1135 | 1160 | 1179 | 1228 |
| 467 | 428 | 389 | 10000 | 424 | 473 | 521 | 527 | 541 | 565 | 633 | 10000 | 1046 | 983 | 1041 | 1126 | 1083 | 1123 | 1159 | 1232 |
| 404 | 375 | 373 | 377 | 421 | 389 | 433 | 480 | 514 | 573 | 627 | 10000 | 1040 | 979 | 1008 | 1037 | 1026 | 10000 | 1333 | 343 |
| 345 | 283 | 283 | 372 | 394 | 381 | 392 | 474 | 536 | 628 | 634 | 10000 | 95 | 907 | 919 | 972 | 962 | 10000 | 1329 | 26 |
| 319 | 275 | 249 | 316 | 332 | 353 | 364 | 10000 | 842 | 878 | 852 | 10000 | 861 | 890 | 824 | 874 | 948 | 10000 | 1242 | 1243 |
| 259 | 213 | 248 | 306 | 301 | 334 | 420 | 10000 | 807 | 84 | 756 | 770 | 773 | 850 | 799 | 10000 | 10000 | 10000 | 1186 | 15 |
| 252 | 194 | 282 | 291 | 281 | 348 | 390 | 10000 | 755 | 755 | 725 | 731 | 772 | 835 | 786 | 828 | 880 | 10000 | 1091 | 1072 |
| 153 | 174 | 261 | 252 | 258 | 10000 | 10000 | 10000 | 700 | 720 | 705 | 706 | 770 | 799 | 785 | 833 | 858 | 10000 | 1014 | 1060 |
| 114 | 173 | 229 | 192 | 187 | 201 | 228 | 10000 | 664 | 64 | 657 | 69 | 75 | 73 | 763 | 842 | 856 | 10000 | 1003 | 05 |
| 112 | 128 | 147 | 148 | 174 | 262 | 276 | 10000 | 590 | 57 | 580 | 67 | 66 | 70 | 789 | 791 | 836 | 915 | 986 | 04 |
| 37 | 111 | 189 | 214 | 277 | 319 | 344 | 10000 | 503 | 512 | 536 | 607 | 61 | 708 | 806 | 843 | 903 | 946 | 987 | 01 |
| 33 | 116 | 186 | 246 | 285 | 309 | 353 | 452 | 468 | 545 | 616 | 678 | 703 | 765 | 786 | 818 | 882 | 904 | 988 | 106 |
Финальными клетками для робота могут быть ячейки: D29, H39, L32, R37 и U23.
Определим минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки. Для этого введем формулу:=МИН(D29;H39;L32;R37;U23). Значение минимального начального запаса энергии, который позволит роботу добраться до какой-нибудь финальной клетки, — 228.
Определим минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Для этого введем формулу:=МАКС(D29;H39;L32;R37;U23). Значение минимального начального запаса энергии, который позволит роботу добраться до любой финальной клетки, — 1339.
Ответ: 228&1339.

