Задача "замкнутая последовательность"

Question

Задача с сайта для подготовки к ЕГЭ по информатике (замкнутая последовательность) Не знаю как вообще нужно решать эту задачу. Помогите, пожалуйста!

На вход программы поступает последовательность натуральных чисел, не превышающих 10000. Последовательность замыкается в кольцо, то есть первый элемент последовательности можно считать следующим после последнего элемента. Например, последовательности 1, 2, 3, 4, 5 и 2, 3, 4, 5, 1 описывают одну и ту же замкнутую последовательность. Хорошей последовательностью называется последовательность длиной не менее 2, в которой сумма всех значений кратна сумме первого и последнего элементов этой последовательности. Например, последовательность 2, 3, 4, 5, 2 является хорошей, так как сумма элементов последовательности 2+3+4+5+2=16 кратна сумме первого и последнего элементов 2+2=4. Необходимо разделить последовательность на две хорошие подпоследовательности. В качестве ответа приведите сумму четырёх чисел – первых и последних чисел в этих подпоследовательностях. Если есть несколько вариантов разделения последовательности на две хороших, приведите максимальное значение суммы.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (4 ≤ N ≤ 50 000) – количество элементов в замкнутой последовательности. В каждой из следующих N строк записаны числа, входящие в последовательность в том порядке, в котором они расположены в последовательности.

Пример входного файла:

7

1

5

2

9

4

2

6

Данную последовательность можно разделить на две подпоследовательности двумя способами: [2, 9] и [4, 2, 6, 1, 5] – искомая сумма 2+9+4+5 = 20 или [9, 4] и [2, 6, 1, 5, 2] – искомая сумма 9+4+2+2 = 17. Ответ: 20. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

ОТВЕТЫ НА ФАЙЛЫ:
228 на файл А
3212 на файл В

P.s. Задача решена. Только второй файл обрабатывается 15 минут. Если знаете как оптимизировать, пожалуйста, пришлите код

s = [int(i.strip()) for i in open('путь до файла', 'r').readlines()][1:]

#   [1, 5, 2, 9, 4, 2, 6]

result = 0
                             #                                                 ↓
for i in range(2, len(s)-2): # делим массив начиная со второго элемента: [1, 5, 2, 9, 4, 2, 6]
   print(i)
   para_right = []
   para_left = []

   # Сохраняем левую часть: left = [1, 5]
   left = s[i-1:-len(s)-1:-1] + s[len(s)-1:i+1:-1]

   # Сохраняем правую часть: right = [2, 9, 4, 2, 6]
   right = s[i:len(s)] + s[0:i-2]

   # Префиксные суммы
   right_sum = 0
   left_sum = 0

   # Перебераем массив right, чтобы найти подходящие пары
   for j in range(len(right)):
      right_sum += right[j]
      qwe = right[j] + right[0]
      if right_sum % qwe == 0:
         para_right.append(right[0:j+1])

   # Перебераем массив left, чтобы найти подходящие пары
   for j in range(len(left)):
      left_sum += left[j]
      qwe = left[j] + left[0]
      if left_sum % qwe == 0:
         para_left.append(left[0:j+1])

   # Сравниваем пары и находим те, суммарная длина которых равна длине изначального массива
   for i in para_right:
      for j in para_left:
         if len(i) + len(j) == len(s):
            result = max(i[0] + i[-1] + j[0] + j[-1], result)

print(result)

Answer 1

Алгоритм квадратичный, работает примерно полминуты.

def seqs(a):
    n = len(a)
    psums = [0]*(n+1)
    for i in range(n):
        psums[i+1] = psums[i] + a[i]
    maxs = 0
    for l in range(n-2):
        for r in range(l+1, n):
            if n - (r-l+1) >= 2:
                e1 = a[l] + a[r]
                s = psums[r+1]-psums[l]
                if s % e1 == 0:
                    e2 = a[l-1] + a[(r+1) % n]
                    if (psums[-1] - s) % e2 == 0:
                        maxs = max(maxs, e1+e2)
    return maxs

БЛОГ НА HUSL

Задача "замкнутая последовательность"

Ответы (1 шт):