11 класс·высокий уровень

Определите максимальную и минимальную денежные суммы, среди всех

Условие

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

Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную. Задание 18Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями. Пример входных данных: 1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Ответ:

Рисунок к задаче

Ответ

Ответ и полный разбор откроются после входа

Посмотреть ответ

Решение по шагам

Как рассуждать

Решение. Сначала найдем максимальную сумму. Будем работать с областью A22:T41. В ячейку A22 впишем значение ячейки A1. В ячейку B22 запишем формулу =A22+B1 и проведем до T21. В ячейку A23 впишем формулу =A22+A2 и проведем вниз до A41. Теперь выделим желтым цветом ячейки, рядом с которыми стоят стены, как показано на картинке: 99	176	242	285	358	429	457	515	524	574	654	698	773	799	826	840	896	972	1001	1018
116
142
212
284
304
322
385
477
551
601
684
720
762
823
874
935
968
1044
Для всех ячеек, которые не выделены будет справедлива формула, записанная в B23, а именно =МАКС(A23;B22)+B2. В остальные ячейки мы можем попасть либо только справа, либо только слева, либо только сверху. Ещё выделим углы зелёным цветом и будем находить максимальное значение среди значений в выделенных «угловых» ячейках. Таким образом, должна получиться такая таблица: 99	176	242	285	358	429	457	515	524	574	654	698	773	799	826	840	896	972	1001	1018
116	196	302	376	443	501	509	590	634	646	669	710	806	845	912	947	1018	1032	1101	1113
142	203	350	401	465	554	589	648	723	799	829	902	910	1001	1079	1160	1197	1272	1297	1314
212	291	389	437	479	633	639	695	782	824	909	945	956	1062	1115	1210	1298	1372	1383	1396
284	361	422	471	493	664	706	704	848	893	948	999	1051	1131	1216	1253	1346	1436	1464	1488
304	410	453	477	516	727	745	717	861	901	957	1018	1069	1198	1262	1312	1425	1477	1501	1513
322	485	549	592	575	739	755	735	875	909	976	1026	1077	1238	1321	1402	1475	1518	1522	1540
372	552	619	664	623	787	802	743	889	921	985	1033	1086	1308	1377	1452	1556	1617	1567	1578
385	612	679	752	690	850	861	748	902	940	998	1053	1097	1347	1437	1514	1591	1688	1581	1589
477	667	704	823	729	887	907	920	939	951	960	968	980	1369	1463	1530	1628	1766	1629	1650
551	741	833	915	787	927	939	945	954	965	983	1003	1008	1424	1515	1595	1677	1783	1692	1706
601	783	881	944	886	988	999	1014	1028	1034	1051	1066	1074	1452	1585	1625	1752	1809	1733	1758
684	865	911	973	957	1044	1064	1071	1089	1094	1104	1120	1138	1463	1599	1677	1811	1876	1774	1797
720	903	972	1006	1015	1122	1133	1195	1257	1272	1303	1365	1167	1518	1624	1713	1863	1894	1838	1854
762	948	1066	1151	1240	1303	1320	1342	1419	1471	1515	1580	1199	1581	1635	1787	1916	1972	1866	1883
823	980	1091	1236	1282	1382	1450	1514	1550	1575	1628	1684	1245	1631	1690	1761	1823	1867	1909	1930
874	1057	1191	1288	1388	1404	1500	1555	1617	1662	1682	1696	1324	1700	1763	1833	1884	1907	1943	1950
935	1094	1283	1387	1436	1474	1517	1600	1665	1719	1792	1855	1388	1766	1828	1865	1893	1984	2044	2115
968	1130	1371	1471	1544	1620	1658	1736	1752	1828	1864	1881	1404	1785	1841	1898	1918	2000	2081	2153
1044	1203	1447	1500	1593	1648	1674	1809	1863	1893	1937	1981	1453	1797	1877	1969	2039	2095	2113	2167

Чтобы найти максимальное значение, в любую свободную ячейку впишем формулу =МАКС(L41;R36;T41) и получим ответ 2167.Теперь, чтобы найти минимальное значение, воспользуемся автозаменой. Нажмем на клавиатуре «Ctrl + H», откроется окошко, в котором в строке «Найти» необходимо вписать «МАКС», а в строке «Заменить на» написать «МИН» и нажать на кнопку «Заменить все»: [рисунок] После чего в той же ячейке вместо 2167 будет написано

Осталось ещё 1 шаг

Полный разбор с проверкой ответа

Получить полное решение

Бесплатно · займёт минуту

Другие задачи по теме «Робот-сборщик монет»

Какую максимальную сумму могут иметь выбранные числа?В ответе запишите11 классКакую максимальную сумму могут иметь выбранные числа?В ответе запишите11 классКакую максимальную сумму могут иметь выбранные числа?В ответе запишите11 классКакую максимальную сумму могут иметь выбранные числа?В ответе запишите11 классОпределите максимальную и минимальную денежные суммы, которые может11 класс

Похожая задача?Сфотографируйте своё условие — ИИ разберёт его по шагам так же