Здравствуйте! В алгоритме "27-78.py" есть ошибки:
1) Если самая длинная цепочка будет начинаться с первого члена последовательности и этот член будет кратен 73, то длина цепочки определится неверно. Связано это с тем, что в tailSum хранится i отсчитывающееся с единицы, а не нуля, а в начальных значениях занесен 0.
Данные:
3
73
2
73
Алгоритм выдаст ответ 4, хотя у нас всего 3 члена последовательности.
2) maxSum определяется неверно, потому что x слишком рано прибавляется к totalSum и в tailSum получается, что хранится сумма хвоста, которую нужно вычесть + первый член цепочки, для которой вычисляется сумма.
Данные:
8
145
2
1
2
6
28
10
67
Правильный ответ 3 (145 + 2 + 1 = 148, 148 / 37 = 4 и (145 + 1) / 73 = 2), алгоритм же выдаст 4 с максимальной суммой 105, что неправильно. Во-первых, максимальная сумма будет 111 (6 + 28 + 10 + 67), но алгоритм вычитает первый член цепочки и получается 105. Во-вторых, 148 больше 111, но поскольку алгоритм каждый раз вместе с tailSum вычитает первый член цепочки, получается что он сравнивает две суммы (148 - 145) и (111 - 6).
На всякий случай сам алгоритм:
K, M = 37, 73
F = open("27.txt")
N = int( F.readline() )
tailSum = [ [0] + [None]*(K-1) ]
for i in range(M-1):
tailSum.append( [None]*K )
tailLen = [[0]*K for i in range(M)]
maxSum, minLen = 0, 0
totalSum = 0
r = 0
for i in range(1,N+1):
x = int( F.readline() )
totalSum += x
ri = x % M
if tailSum[ri][r] == None:
tailSum[ri][r] = totalSum
tailLen[ri][r] = i
r0 = (M - ri) % M
r = totalSum % K
if tailSum[r0][r] != None:
curSum = totalSum - tailSum[r0][r]
curLen = i - tailLen[r0][r] + 1
if curSum > maxSum or \
(curSum == maxSum and curLen < minLen):
maxSum = curSum
minLen = curLen
F.close()
print( minLen )