Задание 27 КЕГЭ: чем отличается решение на 1 балл от решения на 2 балла?
Задание 27 — обработка последовательности чисел. Слышал, что там два теста: A на полный балл и B, где данных очень много. Не понимаю, в чём принципиальная разница в коде и стоит ли вообще пытаться на 2 балла, если я не олимпиадник.
2 ответа
Разница принципиальная и про неё стоит знать.
Тест A (1 балл): данных мало, файл целиком влезает в память. Можно прочитать всё в список и считать в лоб, даже двойным циклом. Решение пишется просто:
a = [int(x) for x in open('A.txt')][1:] # пропускаем первую строку с количеством
# дальше любая прямолинейная обработка, даже O(n^2)
Тест B (2 балла): данных миллионы, и важны два ограничения: (1) нельзя хранить весь массив — память не позволяет, читаешь по одному числу; (2) нельзя двойной цикл — не уложишься в тайм-лимит, нужен один проход O(n).
Типичная идея для B: идёшь по числам по одному, поддерживаешь нужные минимумы/остатки/частичные максимумы "на лету", не возвращаясь назад.
Стоит ли пытаться: возьми гарантированный 1 балл за тест A — он почти всегда несложный. Второй балл бери, если осталось время и видишь идею однопроходного решения. Для 90 баллов одного балла за 27 обычно достаточно.
Ключевая мысль для теста B: читай файл построчно в цикле for line in open(...), а не readlines() — тогда массив в памяти не висит. И обрабатывай каждое число сразу, поддерживая нужные переменные (например, лучший подходящий остаток среди уже прочитанных). Если в задаче надо "для каждого элемента найти лучший предыдущий" — храни не все предыдущие, а только нужную сводку (минимум по остаткам и т.п.). Это и есть переход от O(n²) к O(n).