РЕШУ ЕГЭ — информатика

Задания

Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя.

Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной.

На поле может быть несколько финальных клеток.

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

Задание 18

Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-⁠нибудь финальной клетки.

Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.

В обоих заданиях энергии должно хватить и на прохождение финальной клетки.

Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.

Ответ:

Решение. Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.

В ячейку B23 напишем значении =B2.

Для каждой ячейки левого столбца это будет сумма энергии текущей ячейки и ячейки сверху от текущей. Внесем в ячейку B24 формулу =B23+B3 и скопируем за маркер вниз до ячейки B42.

Для каждой ячейки строки это будет сумма энергии текущей ячейки и ячейки слева от текущей. Внесем в ячейку С23 формулу =B23+C2 и скопируем за маркер вправо до ячейки U23.

Далее в ячейку 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.

№ п/п	№ задания	Ответ
1	61364	324 1481

Ключ