Question

Задачка на питоне , помогите решить)

Answer 1

n = int(input())

a = [int(i) for i in input().split()]

pos = [0] + [-1] * (n - 1)

prefSum = 0

for i in range(n):

   prefSum = (prefSum + a[i]) % n

   if (pos[prefSum] != -1):

       print(pos[prefSum] + 1, i + 1)

       exit()

   pos[prefSum] = i

print("-1 -1")

Надеюсь, такое сможет пройти). Идея в том, что мы считываем массив и идём по всем i є [1; n] ([0; n - 1] в 0-индексации), параллельно добавляя текущий элемент массива (a[i]) к префикс-сумме (к сумме от начала массива до текущего элемента (далее - S[i])). Массив pos состоит из таких элементов, что pos[x] равен последнему из на данный момент рассмотренных индексов (j<i), что S[j] по модулю n дает остаток х. Идя по данному массиву, мы заполняем этот массив. Если в какой-то момент мы узнаем о существовании таких элементов х и у (x < y), что S[x] % n = S[y] % n, то мы получаем следующее:

S[x] % n = S[y] % n

S[y] % n - S[x] % n = 0

(S[y] - S[x]) % n = 0

((a[0] + a[1] + ... + a[x - 1] + a[x] + a[x + 1] + ... + a[y])  - (a[0] + a[1] + ... + a[x])) % n = 0

(a[x + 1] + a[x + 2] + ... + a[y]) % n = 0, а подобный массив нам и нужен.