Разобрать структуру самого сложного задания 27 и закрепить весь курс письменным разбором программы по чек-листу и смешанной практикой.
Специфика задания 27 и идея оптимального алгоритма
Задание 27: большой массив, эффективность и однопроходное решение
Задание 27 — самое сложное в КЕГЭ по информатике. Оно тоже проверяется автоматически: ответ вводится на компьютере в формате, указанном в условии, — это может быть одно число, несколько чисел или пары чисел; эксперта нет. Сложность в том, что файл может содержать очень большое количество чисел, и наивное решение (загрузить всё в список, затем перебирать все возможные комбинации) может не уложиться в ограничение по времени или памяти.
Главная идея оптимального решения — однопроходная (потоковая) обработка: читаем числа по одному и обновляем только нужные вспомогательные переменные, не сохраняя весь массив. Для задач, связанных с делимостью и суммами подотрезков, классический приём — частичные суммы с группировкой по остаткам. Например, если нужно найти количество подотрезков с суммой, кратной k, достаточно хранить счётчик для каждого возможного остатка (словарь из k значений), а не все суммы.
При разборе задания 27 полезно ответить на чек-лист вопросов: что именно мы считаем? какие переменные нужны и что они хранят в каждый момент времени (инвариант)? как обрабатывается первый и последний элемент (граничные случаи)? проверяет ли алгоритм все возможные комбинации или только нужные?
На экзамене код пишется на языке по выбору (Python, C++, C#, Pascal, Java). Для задания 27 на Python особенно важно избегать вложенных циклов O(n²) при большом n — они могут не успеть выполниться. Цель — линейный или O(n log n) алгоритм.
Lesson notes
Задание 27: большой массив, эффективность и однопроходное решение
Задание 27 — самое сложное в КЕГЭ по информатике. Оно тоже проверяется автоматически: ответ вводится на компьютере в формате, указанном в условии, — это может быть одно число, несколько чисел или пары чисел; эксперта нет. Сложность в том, что файл может содержать очень большое количество чисел, и наивное решение (загрузить всё в список, затем перебирать все возможные комбинации) может не уложиться в ограничение по времени или памяти.
Главная идея оптимального решения — однопроходная (потоковая) обработка: читаем числа по одному и обновляем только нужные вспомогательные переменные, не сохраняя весь массив. Для задач, связанных с делимостью и суммами подотрезков, классический приём — частичные суммы с группировкой по остаткам. Например, если нужно найти количество подотрезков с суммой, кратной k, достаточно хранить счётчик для каждого возможного остатка (словарь из k значений), а не все суммы.
При разборе задания 27 полезно ответить на чек-лист вопросов: что именно мы считаем? какие переменные нужны и что они хранят в каждый момент времени (инвариант)? как обрабатывается первый и последний элемент (граничные случаи)? проверяет ли алгоритм все возможные комбинации или только нужные?
На экзамене код пишется на языке по выбору (Python, C++, C#, Pascal, Java). Для задания 27 на Python особенно важно избегать вложенных циклов O(n²) при большом n — они могут не успеть выполниться. Цель — линейный или O(n log n) алгоритм.