Alterna · 40.3 — Динамика и эффективная обработка данных

Для ЕГЭ №27 одного правильного ответа мало: полный перебор пар O(n²) заменяют состоянием, которое обновляется за один проход.

суть и практика11 классОГЭ №6/16ЕГЭ №16/17/23–27

Как это устроено

Большие данные требуют не только верной формулы, но и правильного объёма работы. Сначала оцени сложность, затем сохрани минимальное состояние, достаточное для следующего шага.

O(n²). Перебор всех пар быстро становится непригодным на сотнях тысяч значений.

Один проход. Каждый вход читается один раз; время обычно O(n).

Класс остатка. Для делимости по k достаточно хранить лучшие кандидаты k классов.

Префикс. Накопленная сумма или минимум до текущей позиции заменяет повторный пересчёт отрезка.

Один пример в исполнении

Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.

В задаче о паре с суммой, кратной k, для текущего остатка r нужен лучший предыдущий элемент остатка (-r) % k. Сначала текущий элемент проверяют как правую границу, затем обновляют его класс; иначе один элемент может образовать пару сам с собой. В конкретной задаче ЕГЭ №27 формат результата задаётся условием; если есть ограничение расстояния между индексами, его нужно отражать в состоянии отдельно.

Карта алгоритмаЧитай слева направо, затем запускай код.

1Начало
2Взять значение
3Найти его остаток
4Вычислить нужный предыдущий остаток
5Использовать класс состояния

Запомнить

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

Синтаксис этой страницы

[None] * k

Создаёт массив k независимых ссылок на неизменяемое None.

value % k

Даёт класс остатка value при k > 0.

(-value) % k

Находит остаток, дополняющий value до кратности k.

max

Обновляет лучший найденный ответ.

is None

Проверяет отсутствие кандидата; не путай с == 0.

for value in values

Один линейный проход по данным.

print

Выводит договорённый ответ; no-solution случай должен быть описан условием.