1

Необходимо найти самый большой непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3.

Входные данные

В первой строке входного файла содержится число N≤100000. Во второй строке входного файла следуют N чисел, по модулю не превосходящих 109 — элементы массива.

Выходные данные

Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, то выведите фрагмент с минимальным индексом начала.

Если ответа не существует, то выведите единственное число −1.

Примеры
Ввод
Вывод
4
1 2 3 4
1 3
5
1 2 3 4 5
1 5

n = int(input())
k = []
a = list(map(int, input().split()))
p = [0]*(n+1)
for i in range(1, n+1):
    p[i] = (p[i-1] + a[i-1]) % 3
for i in range(len(p)):
    if p[i] == 0:
        k.append(i)
if len(k) < 2:
    print(-1)
else:
    print(k[0] + 1, k[-1])

помогите решить задачу и доработать мой код, он не проходит все тесты

1 ответ 1

1

Приведённый код учитывает только фрагменты, кумулятивная сумма (p[]) которых равна 0 по модулю 3. Однако подходят и фрагменты, и начало, и конец которых имеют одинаковые p[] со значением 1 или 2.

Поэтому стоит завести список начал и список концов длиной 3

s = [-1] * 3
e = [-1] * 3
p = 0  #список ведь хранить ни к чему
maxlen = 0
mmax = -1
m = 0
for i in range(n):
    if s[m] < 0:
        s[m] = i
    p += a[i]
    m = p % 3
    if s[m] >=0:
        e[m] = i
        if i - s[m] + 1 > maxlen:
            maxlen = i - s[m] + 1
            mmax = m
if mmax >=0:
    print(s[mmax] + 1, e[mmax] + 1)
else:
    print(mmax)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.