Подпоследовательность с максимальной суммой, кратной 43.

 

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

 

Рассмотрим следующую задачу из демонстрационного варианта ФИПИ ЕГЭ по информатике 2022 г. (она также включена в вариант 3 на сайте Полякова):

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10⁸). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Пример входного файла:

7
21
13
9
19
17
26
95

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Ответ: 2.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

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

Пусть S(n) - это сумма элементов последовательности с её начала и до элемента с индексом n, включая этот элемент. Тогда сумма подпоследовательности от элемента с индексом k+1 до элемента с индексом m есть S(m)-S(k). А если у чисел S(k) и S(m) одинаковые остатки от деления на 43, то сумма указанной подпоследовательности делится на 43.

Если же частичная сумма дает остаток от деления на 43, равный нулю, то у нас есть подпоследовательность от начала исходной последовательности до текущего элемента.

Построим следующую таблицу для исходных данных, приведенных в задаче:

n	a[n]	S(n)	S(n)%43
0	21	21	21
1	13	34	34
2	9	43	0
3	19	62	19
4	17	79	36
5	26	105	19
6	95	200	28

Мы видим, что сумму, кратную 43, имеют подпоследовательности от a[0] до a[2] и от a[4] до a[5].

Сумма подпоследовательности легко находится как разность частичных сумм, а длина - как разность индексов начала и конца.

Так как все элементы последовательности - натуральные числа, то чем длиннее последовательность, тем больше её сумма. 

Теперь алгоритм достаточно ясен. Для каждого остатка от деления частичной суммы на 43 запоминаем самый первый случай его появления в последовательности и значение частичной суммы. Читаем новый элемент последовательности, получаем частичную сумму и находим остаток от деления ее на 43. Если такой остаток уже был ранее - то у нас новая подпоследовательность с суммой, делящейся на 43 без остатка. Если же такого остатка не было - то запоминаем индекс его первого появления в массиве first и значение частичной суммы - в массиве firstsum. 

Признак того, что данного остатка нам ранее не встречалось - это значение -1 у соответствующего элемента массива first. 

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

Особый случай - частичная сумма, кратная 43. В этом случае начало подпоследовательности совпадает с началом последовательности. Поэтому элементам массивов first и firstsum с индексом 0 присваиваются соответствующие значения.

Программа на Питоне, реализующая данный алгоритм, приведена ниже.

f=open("in.txt")
n=int(f.readline())
l=1000000000
m=0
s=0
k=43

first = [-1]*k
firstsum = [-1]*k
firstsum[0] = 0
first[0] = -1

for i in range(n):
    s += int(f.readline())
    r=s%k
    if firstsum[r] < 0:
        firstsum[r] = s
        first[r] = i
    else:
        mym = s - firstsum[r]
        myl = i - first[r]

        if mym > m:
            m=mym
            l=myl
        elif mym == m:
            if myl < l:
                l = myl

print(l)

(c) Ю.Д.Красильников, 2021 г.