Задание 27 ЕГЭ по информатике: как подступиться

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

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

Два файла и что за ними стоит

К задаче приложены два файла с данными. В первом данных немного, и проходит любое решение, даже самое неуклюжее. Во втором их так много, что перебор всех пар или всех отрезков не закончится: программа будет работать неприлично долго. Отсюда обычная картина. Первый ответ получают почти все, кто дошёл до задачи, второй — те, кто увидел заготовку быстрого алгоритма.

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

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

Первый приём: префиксные суммы

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

Покажу на маленьком наборе. Даны числа 3, 1, 2, 4, нужно посчитать, сколько отрезков подряд идущих чисел имеют сумму, кратную трём. Префиксные суммы вместе с нулём в начале: 0, 3, 4, 6, 10. Остатки от деления на три: 0, 0, 1, 0, 1. Сумма отрезка кратна трём ровно тогда, когда остатки на его концах совпадают. Остаток 0 встречается три раза, и это три пары. Остаток 1 встречается два раза, и это ещё одна пара. Всего четыре отрезка: [3], [1, 2], [2, 4] и [3, 1, 2]. Перебором получается то же самое, только действий выходит столько, сколько всего отрезков, а префиксные суммы требуют по одному действию на число.

Кажется, что приём годится лишь для частного случая, но он возвращается в разных обличьях: «сумма кратна k», «сумма не меньше заданной», «чётное число нечётных». Если один раз разобрать его на бумаге, на экзамене вы его узнаете.

Второй приём: две отметки

Другая знакомая ситуация: надо найти самый длинный (или самый короткий) отрезок со свойством, которое при добавлении чисел только портится или только улучшается. Например, самый длинный отрезок, в котором сумма не превосходит заданного числа, а все числа положительны.

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

Попробуйте на числах 2, 1, 3, 1, 1, 2 и пределе 5. Отрезок растёт: 2, потом 2 и 1 (сумма 3). Добавили 3, сумма стала 6, больше предела, значит, начало сдвигаем и теряем двойку: остались 1 и 3, сумма 4. Добавили единицу, сумма 5, длина три. Следующая единица даёт 6, сдвигаем начало, остаются 3, 1, 1 с суммой 5. Потом входит последняя двойка, сумма 7, начало сдвигается один раз, остаются 1, 1, 2 с суммой 4. Лучшая длина за весь проход равна трём, и перебор всех отрезков даст тот же ответ, потому что никакие четыре подряд идущих числа в сумме не укладываются в предел. Заметьте, что ни разу не пришлось возвращаться назад.

Условие «числа положительны» поставлено ради дела. Если среди чисел встречаются отрицательные, двигать начало вперёд безопасно уже нельзя: сумма от этого может как упасть, так и вырасти, и приём ломается. Это типичная ловушка. Человек выучил схему и не выучил условия её применимости, поэтому на маленьком файле решение даёт верный ответ, а на большом неверный, и проверить большой файл нечем.

Третий приём: хранить только нужное

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

Читать большой файл целиком в список можно не всегда, и привычка обрабатывать поток на лету экономит память и нервы. Если вы пишете на Python, это чтение построчно. На C++ добавляется внимание к типам: сумма большого количества чисел легко не помещается в обычное целое, и переполнение даёт ответ, который выглядит правдоподобно и неверен.

Вот типичная картина. Нужно найти наибольшую разность между числом и самым маленьким числом, которое стоит перед ним. Для чисел 5, 3, 8, 2, 9 программа идёт слева направо и помнит одно значение, наименьшее из уже увиденных. На восьмёрке минимум равен трём, разность пять. Затем минимум становится двойкой, и на девятке разность семь, это и есть ответ. Список всех пар здесь не нужен совсем, хватает одной переменной.

Поэтому перед запуском на большом файле стоит проверить программу на крошечном наборе с известным ответом. Придумайте десять чисел, посчитайте руками, сравните. Две минуты экономят целую задачу, а ошибка, которую находишь на большом файле без эталона, не находится вовсе.

Когда лучше не браться

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

Отказываться от неё совсем я не предлагаю. Порядок подготовки должен идти от дешёвого к дорогому. У ученика с хорошей базой, который хочет максимум, эта задача должна быть отдельной линией с осени, по одной в неделю. Тот, кому для поступления достаточно уверенного среднего результата, вполне может отложить её на весну или оставить. Решение лучше принимать после двух-трёх полных вариантов на компьютере, а не в сентябре по настроению: к зиме по результатам вариантов уже видно, где у вас дыры и сколько баллов на них приходится. Если за зиму середина работы выровнялась, последняя задача перестаёт быть роскошью и становится ближайшим резервом.

Как тренироваться и на чём ломаются сильные

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

Если схема не находится и вы читаете разбор, запишите её одной строкой в тетрадь: «остатки префиксных сумм» или «две отметки, числа положительные». Через два месяца там наберётся с десяток строк, и на новой задаче вы начнёте узнавать знакомую форму. Тетради хватает, чтобы не изобретать на экзамене заново то, что вы однажды уже разбирали.

Язык определяет, сколько вы готовы ждать. Подробно об этом в статье про выбор между Python и C++: на Python удобнее придумывать, на C++ спокойнее ждать. А если слабое место у вас перевод чисел между основаниями, который встречается и внутри других заданий, посмотрите разбор систем счисления. Общий порядок года, в который эта задача вписана отдельной линией, описан в статье о подготовке к ЕГЭ за год.

Сильные ученики ломаются на другом. Самая обидная потеря в этой задаче случается у тех, кто решает её хорошо. Алгоритм придуман верно, программа написана, на малом файле ответ сошёлся, и ученик переходит к большому. Файл читается, ответ получен, ответ вводится. И он неверный, потому что большой файл отличается от малого чем-то незаметным: в нём встречается значение, которого в малом не было. Нулевая сумма, одинаковые числа подряд, отрезок, который начинается в самом начале файла.

Против этого есть дешёвое средство: перед запуском придумать три коротких набора, на которых можно поломать собственное решение. Файл из одного числа, файл из одинаковых чисел, файл, где все числа подходят под условие. Если программа выдержала эти три, шансов на верный ответ заметно больше. На такую проверку уходят минуты, а разбирать, почему ответ неверен, когда времени уже нет, приходится гораздо дольше.

Ещё одна привычка, которую я бы вырабатывал заранее: выводить на экран промежуточные значения на малом файле, пока решение пишется. Увидеть, что префиксные суммы получились именно такими, как вы насчитали руками, куда полезнее, чем гадать по итоговому числу. Когда решение заработало, лишний вывод убирается одной строкой, а если его оставить в программе для большого файла, терминал будет печатать миллионы строк и тормозить сильнее любого перебора. Такое случается с каждым хотя бы раз, лучше пусть это случится на тренировке.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ
• пробное занятие с разбором своей программы

Вопросы и ответы

С какого уровня имеет смысл браться за эту задачу? Когда вы без подсказок решаете задачи середины работы и пишете программы, не отлаживая каждую по полчаса. Раньше можно читать разборы, но решать самому ещё рано.

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

Что делать, если не уверен в быстроте Python? Если решение построено на одном проходе по файлу без вложенных циклов, Python справляется. Если вложенный перебор остался, дело в алгоритме, и переход на C++ даст отсрочку, но не спасение.

Нужна ли для этой задачи математика? Школьной хватит: остатки, сумма, минимум, максимум. Привычка считать на бумаге маленький пример помогает больше, чем любые формулы.

Можно ли держать на экзамене готовые куски кода? Нет, на рабочем месте только то, что установили организаторы. Поэтому шаблон чтения файла и основные приёмы надо знать наизусть.