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

Задания

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

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

В ответе запишите два числа: сначала максимальный расход энергии, затем  — количество пройденных клеток с нечётными значениями.

Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4 × 4):

Задание 18

43	90	2	44
72	30	36	63
62	6	61	42
21	84	49	51

При указанных входных данных максимальный расход получится при движении по маршруту

$43 плюс 90 плюс 72 плюс 30 плюс 36 плюс 63 плюс 61 плюс 84 плюс 49 плюс 51 = 579.$

При этом робот проходит через 5 клеток с нечётными числами (43, 63, 61, 49, 51). В ответе в данном случае надо записать числа 579 и 5.

Ответ:

Решение. Для поиска максимального значения будем работать с областью B23:U42. В ячейку B23 напишем значение =B2.

По строке 23 робот может перемещаться только вправо. Запишем формулу в ячейке C23:

=B23+C2

и скопируем её на весь диапазон C23:U23.

В ячейки столбца B робот может попасть из верхней ячейки или с верхней правой, по диагонали. Запишем формулу в ячейке B24:

=B2+МАКС(B23;C23)

и скопируем её на весь диапазон B24:B42.

Посчитаем возможные ячейки в других столбцах. Запишем формулу в ячейке C24:

=C3+МАКС(B24;C23;B23;D23)

и скопируем её на весь диапазон C24:U42.

В ячейке U42 находится ответ 3864.

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

15	82	181	219	259	304	337	389	417	464	485	556	620	633	692	766	862	882	939	951
137	204	280	373	458	547	567	631	648	692	737	800	836	857	940	007	1097	140	156	1171
111	293	394	523	570	608	701	737	795	882	930	946	973	987	035	1174	1228	1313	318	1393
103	477	557	663	674	710	748	891	959	975	1005	1056	1149	1236	1304	1347	1381	1459	1517	1524
127	567	682	751	784	807	898	1040	1093	1163	1226	1234	1259	1376	1381	1408	1481	1519	1596	1654
57	736	770	863	958	1031	1086	1097	1231	1320	1333	1397	1445	1524	1567	1598	1697	1748	1844	1920
115	865	869	045	080	1121	1157	1323	1404	1444	1519	1532	1584	1667	1762	1860	1926	2001	2098	2105
140	924	1090	1107	1162	1213	1419	1444	1485	1581	1646	1675	1726	1784	1880	1983	2006	2195	2272	2305
86	1151	1154	1177	1222	1455	1530	1567	1617	1719	1748	1840	1890	1951	2064	2103	2283	2345	2357	2396
75	1174	1265	1289	1496	1534	1653	1730	1753	1843	1937	1998	2094	2148	2217	2290	2354	2377	2465	2546
51	1296	1363	1519	1581	1731	1797	1805	1930	1952	2079	2186	2221	2260	2313	2391	2428	2528	2618	2706
74	1371	1614	1684	1748	1889	1929	2022	2082	2146	2246	2271	2301	2366	2413	2455	256	2699	2736	2813
140	1627	1736	1808	1911	1940	2112	2154	2251	2272	2347	2413	2422	2500	2542	2581	2746	2753	2893	2948
99	1831	1926	2003	2023	2125	2244	2303	2306	2382	2475	2500	2570	2580	2671	2777	2870	2964	3023	3064
147	1946	2049	2070	2205	2282	2364	2383	2481	2484	2576	2631	2713	2749	2779	2929	3040	3083	3087	3112
80	2119	2212	2225	2343	2368	2463	2504	2520	2627	2698	2764	2813	2835	2937	3059	3119	3152	3174	3229
165	2258	2352	2367	2391	2486	2578	2664	2699	2759	2836	2916	2944	2991	3157	3224	3273	3308	3338	3425
157	2405	2438	2480	2582	2601	2667	2726	2774	2918	2968	2994	3000	3195	3302	3316	3318	3347	3478	8519
156	2495	2569	2680	2760	2851	2925	2965	2977	3000	3025	3051	3236	3396	3472	3564	3606	3636	3698	3751
108	2659	2699	2848	2936	3019	3113	3129	3156	3240	3265	3338	3458	3519	3659	3683	3718	3781	3860	3864

Скопируем форматирование на первую таблицу и перекрасим все зеленые клетки, содержащие нечетные числа:

15	67	99	38	40	45	33	52	28	47	21	71	64	13	59	74	96	20	57	12
70	23	61	93	85	89	20	64	17	44	45	63	36	21	83	67	90	43	16	15
41	13	21	65	23	38	70	36	58	87	48	16	27	14	28	77	54	85	5	75
62	83	34	93	11	9	11	96	68	16	30	51	93	87	68	43	34	78	58	7
44	10	19	69	33	23	7	81	53	70	63	8	23	72	5	27	22	2	72	58
13	54	19	79	95	73	46	4	68	89	13	64	48	79	43	31	99	51	96	76
61	95	4	87	35	35	36	92	81	40	75	13	52	83	95	98	66	75	97	7
45	55	45	17	41	51	96	25	41	62	65	29	51	22	20	57	5	97	77	33
31	61	3	15	9	36	75	37	36	73	29	92	50	61	81	39	88	62	12	39
14	20	88	24	41	4	86	77	23	90	94	61	96	54	69	7	9	20	69	81
31	31	67	23	47	78	66	8	87	15	81	92	35	39	23	37	37	63	72	88
43	8	95	70	17	92	40	92	60	64	60	25	30	53	22	27	36	81	30	77
97	13	52	60	22	11	90	42	97	21	75	66	9	78	42	17	47	7	80	55
2	95	95	77	20	13	90	52	3	35	62	25	70	10	90	31	93	71	59	41
52	20	46	21	80	38	61	19	98	3	76	55	82	36	2	59	76	43	4	25
28	70	93	13	61	4	80	23	16	51	67	51	49	22	8	19	36	33	22	55
95	46	94	15	23	23	74	86	35	60	72	80	28	47	98	67	49	35	30	87
62	53	33	42	96	19	3	27	15	82	50	26	6	38	78	14	2	9	53	41
94	57	74	98	80	91	74	40	12	23	25	26	41	94	76	92	42	30	62	53
14	90	19	88	85	83	94	16	27	84	25	73	62	47	95	24	35	63	79	4

Наконец, чтобы получить ответ на второй вопрос, посчитаем количество нечетных ячеек и получим 28.

Ответ: 3864 и 28.

№ п/п	№ задания	Ответ
1	51987	3864 28

15	67	99	38	40	45	33	52	28	47	21	71	64	13	59	74	96	20	57	12
70	23	61	93	85	89	20	64	17	44	45	63	36	21	83	67	90	43	16	15
41	13	21	65	23	38	70	36	58	87	48	16	27	14	28	77	54	85	5	75
62	83	34	93	11	9	11	96	68	16	30	51	93	87	68	43	34	78	58	7
44	10	19	69	33	23	7	81	53	70	63	8	23	72	5	27	22	2	72	58
13	54	19	79	95	73	46	4	68	89	13	64	48	79	43	31	99	51	96	76
61	95	4	87	35	35	36	92	81	40	75	13	52	83	95	98	66	75	97	7
45	55	45	17	41	51	96	25	41	62	65	29	51	22	20	57	5	97	77	33
31	61	3	15	9	36	75	37	36	73	29	92	50	61	81	39	88	62	12	39
14	20	88	24	41	4	86	77	23	90	94	61	96	54	69	7	9	20	69	81
31	31	67	23	47	78	66	8	87	15	81	92	35	39	23	37	37	63	72	88
43	8	95	70	17	92	40	92	60	64	60	25	30	53	22	27	36	81	30	77
97	13	52	60	22	11	90	42	97	21	75	66	9	78	42	17	47	7	80	55
2	95	95	77	20	13	90	52	3	35	62	25	70	10	90	31	93	71	59	41
52	20	46	21	80	38	61	19	98	3	76	55	82	36	2	59	76	43	4	25
28	70	93	13	61	4	80	23	16	51	67	51	49	22	8	19	36	33	22	55
95	46	94	15	23	23	74	86	35	60	72	80	28	47	98	67	49	35	30	87
62	53	33	42	96	19	3	27	15	82	50	26	6	38	78	14	2	9	53	41
94	57	74	98	80	91	74	40	12	23	25	26	41	94	76	92	42	30	62	53
14	90	19	88	85	83	94	16	27	84	25	73	62	47	95	24	35	63	79	4

15	67	99	38	40	45	33	52	28	47	21	71	64	13	59	74	96	20	57	12
70	23	61	93	85	89	20	64	17	44	45	63	36	21	83	67	90	43	16	15
41	13	21	65	23	38	70	36	58	87	48	16	27	14	28	77	54	85	5	75
62	83	34	93	11	9	11	96	68	16	30	51	93	87	68	43	34	78	58	7
44	10	19	69	33	23	7	81	53	70	63	8	23	72	5	27	22	2	72	58
13	54	19	79	95	73	46	4	68	89	13	64	48	79	43	31	99	51	96	76
61	95	4	87	35	35	36	92	81	40	75	13	52	83	95	98	66	75	97	7
45	55	45	17	41	51	96	25	41	62	65	29	51	22	20	57	5	97	77	33
31	61	3	15	9	36	75	37	36	73	29	92	50	61	81	39	88	62	12	39
14	20	88	24	41	4	86	77	23	90	94	61	96	54	69	7	9	20	69	81
31	31	67	23	47	78	66	8	87	15	81	92	35	39	23	37	37	63	72	88
43	8	95	70	17	92	40	92	60	64	60	25	30	53	22	27	36	81	30	77
97	13	52	60	22	11	90	42	97	21	75	66	9	78	42	17	47	7	80	55
2	95	95	77	20	13	90	52	3	35	62	25	70	10	90	31	93	71	59	41
52	20	46	21	80	38	61	19	98	3	76	55	82	36	2	59	76	43	4	25
28	70	93	13	61	4	80	23	16	51	67	51	49	22	8	19	36	33	22	55
95	46	94	15	23	23	74	86	35	60	72	80	28	47	98	67	49	35	30	87
62	53	33	42	96	19	3	27	15	82	50	26	6	38	78	14	2	9	53	41
94	57	74	98	80	91	74	40	12	23	25	26	41	94	76	92	42	30	62	53
14	90	19	88	85	83	94	16	27	84	25	73	62	47	95	24	35	63	79	4

Ключ

15	67	99	38	40	45	33	52	28	47	21	71	64	13	59	74	96	20	57	12
70	23	61	93	85	89	20	64	17	44	45	63	36	21	83	67	90	43	16	15
41	13	21	65	23	38	70	36	58	87	48	16	27	14	28	77	54	85	5	75
62	83	34	93	11	9	11	96	68	16	30	51	93	87	68	43	34	78	58	7
44	10	19	69	33	23	7	81	53	70	63	8	23	72	5	27	22	2	72	58
13	54	19	79	95	73	46	4	68	89	13	64	48	79	43	31	99	51	96	76
61	95	4	87	35	35	36	92	81	40	75	13	52	83	95	98	66	75	97	7
45	55	45	17	41	51	96	25	41	62	65	29	51	22	20	57	5	97	77	33
31	61	3	15	9	36	75	37	36	73	29	92	50	61	81	39	88	62	12	39
14	20	88	24	41	4	86	77	23	90	94	61	96	54	69	7	9	20	69	81
31	31	67	23	47	78	66	8	87	15	81	92	35	39	23	37	37	63	72	88
43	8	95	70	17	92	40	92	60	64	60	25	30	53	22	27	36	81	30	77
97	13	52	60	22	11	90	42	97	21	75	66	9	78	42	17	47	7	80	55
2	95	95	77	20	13	90	52	3	35	62	25	70	10	90	31	93	71	59	41
52	20	46	21	80	38	61	19	98	3	76	55	82	36	2	59	76	43	4	25
28	70	93	13	61	4	80	23	16	51	67	51	49	22	8	19	36	33	22	55
95	46	94	15	23	23	74	86	35	60	72	80	28	47	98	67	49	35	30	87
62	53	33	42	96	19	3	27	15	82	50	26	6	38	78	14	2	9	53	41
94	57	74	98	80	91	74	40	12	23	25	26	41	94	76	92	42	30	62	53
14	90	19	88	85	83	94	16	27	84	25	73	62	47	95	24	35	63	79	4