Сумма, делящаяся на три

Question

Необходимо найти самый большой непрерывный фрагмент в массиве 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])

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

Answer 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)

Answer 2

Фух, задача и вправду довольно сложная, если решать ее линейно. Вот мое решение на c++. Что бы вы порекомендовали исправить/отредактировать в коде? Все тесты прошел на сайте: https://edu.sirius.online/#/course/740/6164/task_9241

    #include <bits/stdc++.h> 

    using namespace std;

    int main(){
        int n; cin >> n;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];

        int min0 = 0, min1 = 1e9 + 1, min2 = 1e9 + 1;
        vector<long long> p(n+1);
        for(int i = 1; i < n+1; i++) p[i] = p[i-1] + v[i-1]; 
        for(int i = 1; i < n+1; i++){
            p[i] = (p[i] % 3 + 3) % 3;
            if(i < min1 && p[i] % 3 == 1){
                min1 = i;
            } else if(i < min2 && p[i] % 3 == 2){
                min2 = i;
            }
        }
        int imin, ibest = 0, iminbest = 0;
        for(int i = 1; i < n+1; i++){
            if(p[i] == 0){
                imin = min0;
            } else if(p[i] == 1){
                imin = min1;
            } else if(p[i] == 2){
                imin = min2;
            }
            if(i - imin > ibest - iminbest){
                ibest = i; iminbest = imin;
            }
        }
        ibest == iminbest ? cout << -1 : cout << iminbest+1 << ' ' << ibest;
    }

БЛОГ НА HUSL

Сумма, делящаяся на три

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