[None] * kСоздаёт массив k независимых ссылок на неизменяемое None.
Для ЕГЭ №27 одного правильного ответа мало: полный перебор пар O(n²) заменяют состоянием, которое обновляется за один проход.
суть и практика11 классОГЭ №6/16ЕГЭ №16/17/23–27
01
Как это устроено
Большие данные требуют не только верной формулы, но и правильного объёма работы. Сначала оцени сложность, затем сохрани минимальное состояние, достаточное для следующего шага.
O(n²). Перебор всех пар быстро становится непригодным на сотнях тысяч значений.
Один проход. Каждый вход читается один раз; время обычно O(n).
Класс остатка. При подсчёте пар с суммой, кратной k, достаточно хранить count для k классов остатков.
Префикс. Накопленная сумма или минимум до текущей позиции заменяет повторный пересчёт отрезка.
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
В задаче о числе пар с суммой, кратной k, для текущего остатка r нужны все прежние элементы остатка (-r) % k: их количество хранит count[need]. Сначала текущий элемент проверяют как правую границу и прибавляют count[need] к ответу, затем увеличивают count[r]; иначе один элемент образует пару сам с собой. Для другой цели, например максимальной суммы пары, вместо счётчика хранят лучший кандидат класса.
Карта алгоритмаЧитай слева направо, затем запускай код.
- 1Начало
- 2Взять значение
- 3Найти его остаток
- 4Вычислить нужный предыдущий остаток
- 5Использовать класс состояния
03
Запомнить
- Сначала проверяй пару с прежними данными, затем обновляй класс текущим элементом.
- Определи поведение при отсутствии допустимой пары.
- Для ограничения расстояния добавляй элементы в состояние только после нужной задержки.
Синтаксис этой страницы
value % kДаёт класс остатка value при k > 0.
(-value) % kНаходит остаток, дополняющий value до кратности k.
maxОбновляет лучший найденный ответ.
is NoneПроверяет отсутствие кандидата; не путай с == 0.
for value in valuesОдин линейный проход по данным.
printВыводит договорённый ответ; no-solution случай должен быть описан условием.