Отправлено: 12.07.22 11:32. Заголовок: №4507 (27.78) ошибки в алгоритме

Здравствуйте! В алгоритме "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 ) 
 

 Отправлено: 09.08.22 14:26. Заголовок: Спасибо за тщательны..

Спасибо за тщательный анализ и примеры. Решение исправлено.