Разбор задания № 27 ЕГЭ по информатике (динамическое программирование)

Условие задачи № 27 ЕГЭ по информатике

На вход программы поступает последовательность из целых положительных чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была максимальной и делилась на 89, а также ее длину.

Если таких подпоследовательностей несколько, выбрать такую, у которой длина меньше.

Входные данные
Файл A
Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 68000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000. Программа должна вывести длину найденной последовательности.

Пример входного файла:
8
2
3
4
93
42
34
5
95

Для делителя 50 при указанных входных данных значением искомой суммы должно быть число 100 (3 + 4 + 93 или 5 + 95). Следовательно, ответ на задачу - 2. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Решение на 1 балл (полный перебор)

Решение на 1 балл основывается на полном переборе и проходит по тесту A. Считываем все данные в список и с помощью вложенного цикла перебираем все возможные длины. Для каждой такой последовательности вычисляем сумму. (сумма элементов среза списка)

Если текущая сумма превышает максимальную, то перезаписываем максимальную сумму и сохраняем новую длину подпоследовательности. В случае равенства сумм, сравниваем текущую длину и минимальную длину и сохраняем ту, которая меньше.

f = open('test.txt', 'r') # открываем файл для чтения
n = int(f.readline())
#mass = [int(x) for x in f.readlines()]

mass = list(map(int, f.readlines())) # считываем в список чисел
# print(mass)

const = 50 # число для проверки кратности
max_sum = 0 # инициализация максимальной суммы

for i in range(n):
   for j in range(i, n):
      s = sum(mass[i: j + 1]) # вычисляем сумму на отрезке списка

      if s % const == 0 and s > max_sum: # если сумма кратна заданному числу и превышает максимальную сумму
         max_sum, min_dlina = s, j - i + 1 # перезаписываем максимальную сумму, сохраняем минимальную длину
      if s % const == 0 and s == max_sum: # в случае равенства сумм при необходимости перезаписываем минимальную длину
         min_dlina = min(min_dlina, j - i + 1)

print(min_dlina)

Решение на 2 балла (эффективный алгоритм)

Будем использовать словарь, в котором ключом будет являться остаток при делении текущей суммы на 89, а значением ключа будет являться кортеж, первый элемент которого хранит текущую сумму, а второй – порядковый номер числа. (начиная с 1)

Используем метод динамического программирования, при котором нам нужно запоминать все возможные значения. Если появился новый остаток, которого не было в словаре, нужно добавить его в словарь. Ключ – остаток при делении суммы на 89, а значение ключа – кортеж из двух чисел. (накопленная сумма и порядковый номер считываемого числа)

Если остаток уже есть в словаре, то нам нужно где-то запомнить разность между текущей накопленной суммой и суммой, хранящейся по этому ключу (остатку) в словаре. Очевидно, что эта разность будет кратна 89. (т.к. остатки совпали)

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

Чтобы найти максимальную разность с минимальным расстоянием, сделаем расстояния отрицательными величинами (будет вычитать из меньшего порядкового номера больший). Тогда минимум превратится в максимум, и для поиска ответа нам будет достаточно использовать функцию max(). Для восстановления ответа нужно не забыть поставить знак минус, т.к. полученные расстояния в списке будут отрицательными величинами.

Программа на языке Python (эффективна по времени и памяти)

f = open('test.txt', 'r')
k, s = 89, 0 # инициализация значения кратности и суммы

mins = {0: (0, 0)} # используем словарь, где ключом будет остаток при делении суммы на величину k
res = [] # список, хранящий подходящие суммы и расстояния

for i in range(1, int(f.readline()) + 1):
   s += int(f.readline()) # накапливаем сумму
   if s % k in mins: # если остаток есть в словаре
      res += [(s - mins[s % k][0], mins[s % k][1] - i)] # вычисляем сумму и расстояние и заносим их как кортеж в список (расстояния будут идти со знаком "-")
   else: # если такого остатка нет в словаре, то добавляем его в словарь
      mins[s % k] = (s, i) # создаем новый ключ словаря, значением ключа будет сумма и текущий порядковый номер
print(-max(res)[1]) # выводим ответ

Данное решение проходит по двум тестам и набирает максимальный балл.