Несмотря на коронавирус и ограничения, связанные с ним, ЕГЭ отменять никто не планирует, поэтому подготовка к нему продолжается. Один из предметов, которые я выбрал для сдачи на ЕГЭ — информатика. Для меня, программиста, этот предмет жизненно необходим при поступлении, а самой интересной в экзамене, на мой программистский взгляд, является последняя, двадцать седьмая задача. Это задание на написание собственной эффективной программы, решающей поставленную в условии задачу. В ходе подготовки к экзамену я прорешал уже не один десяток таких задач, причем разных задач, некоторые из них были попроще, некоторые — посложнее, «поинтереснее». И при решении задач у меня уже выработались некоторые привычки, какую идею где использовать, и такими идеями я хочу поделиться с Вами.
Задача
На вход дается последовательность из n целых положительных чисел, необходимо определить и вывести на экран максимальную сумму пары, составленной из чисел такой последовательности, находящихся в ней на расстоянии не менее 6.
Первые мысли
При чтении такой задачи сразу возникает вопрос: а как это выглядит в последовательности, что числа находятся на расстоянии не менее 6? Думаю, проще будет разобраться на примере. Пусть есть последовательность:
1, 2, 3, 4, 5, 100, 200, 400, 500, …
Видно, что, например, числа, 1 и 200 находятся на расстоянии 6. Номер числа 1 в последовательности — 0 (да-да, давайте все-таки здесь тоже считать с нуля), а номер числа 200 — 6. 6 — 0 = 6. При помощи такого наблюдения понимаем, что расстояние между элементами — разность их индексов.
Решение на 2 балла
Как известно из критериев оценивания этой задачи, можно получить 2 балла, написав неэффективную программу, например, можно перебрать все пары, проверять, больше или равна ли 6 разница индексов, если больше, то считать и сравнивать сумму, обновлять максимум… Но такое решение без труда смогут написать все, кто хотя бы немного знаком с программированием и это не интересно.
«Окно»
Подумав немного дальше, можно обнаружить, что, если выбрать какие-то 7 подряд идущих элементов последовательности, то первый и последний элементы такого «окна» будут находиться как раз на расстоянии 6:
[1, 2, 3, 4, 5, 100, 200], 400, 500, …
Кроме того, последний элемент «окна» гарантированно может стоять в паре с любым, идущим до окна. Например, число 500 может стоять в паре с числами 1, 2 и 3, так как расстояние между первым и последним элементами равно минимально возможному, а расстояние между последним и теми, что были до первого, будет больше минимально возможного.
1, 2, 3, [4, 5, 100, 200, 400, 500], …
Поэтому для проверки всех подходящих пар нам нужно будет запомнить текущую пару в виде двух чисел (обозначим a и b) и для каждого состояния «окна» проверить три пары, обновляя значения a и b при проверке:
- a и последний элемент окна (обозначим y).
- b и y.
- Первый элемент «окна» (обозначим x) и y.
Важно. Проверку делаем только для последнего элемента «окна», так как первый либо уже был когда-то ранее последним, либо стоит в начале последовательности до индекса, равного минимальному расстоянию между элементами в паре, так что его нельзя поставить в пару ни с одним из элементов, идущих до него.
Финальная сталия разработки
Во избежание повторов одинаковых по смыслу кусков кода проверку пар можно вынести в отдельную функцию, остается доделать инициализацию, считывание данных и обновление «окна». В Python, на котором пишу я, это делается красиво. Но везде обновление массива будет рабоать на константное время, так как длина обновляемого массива известна и постоянна. В конце, конечно, необходимо вывести найденную сумму.
Код доступен на GitHub: https://github.com/kormanowsky/ege-27/blob/master/1_window.py.
Всем спасибо за внимание! Если было полезно, поделитесь этим. Оставляйте комментарии, конструктивные замечания, всегда рад услышать обратную связь. Скоро будут новые статьи по теме!
