Find the largest continuous fragment in the array a1, a2, ..., aN whose sum of elements is divisible by three. Input

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

Пояснение: Для решения этой задачи мы будем использовать подход, основанный на префиксных суммах. Префиксные суммы - это суммы элементов массива, начиная от первого элемента до текущего, которые мы можем вычислить заранее. Затем мы используем префиксные суммы для нахождения наибольшего непрерывного фрагмента с суммой элементов, кратной трем.

Мы создаем массив prefix_sums длиной N+1 и инициализируем первый элемент prefix_sums[0] равным 0. Затем мы вычисляем префиксные суммы, используя следующую формулу: prefix_sums[i] = prefix_sums[i-1] + a[i-1]. Теперь у нас есть доступ к сумме подмассива a[i:j] как prefix_sums[j+1] - prefix_sums[i].

Далее мы инициализируем переменные max_length и max_start соответственно равными 0 и -1. Мы также создаем словарь remainders, где ключи - остатки от деления префиксной суммы на три, а значения - индексы этих сумм. Мы используем словарь, чтобы сохранить только самые первые индексы префиксных сумм, имеющих одинаковый остаток. Затем мы перебираем индексы i от 0 до N и для каждого индекса i проверяем остаток от деления prefix_sums[i+1] на три.

Если остаток равен нулю, мы обновляем значения max_length и max_start, если новая длина фрагмента больше предыдущей найденной наибольшей длины. Если остаток не равен нулю, мы проверяем, есть ли в словаре remainders другой фрагмент с остатком, равным остатку текущей префиксной суммы за исключением последних трех элементов. Если это верно, мы снова обновляем значения max_length и max_start.

В конце мы выводим значения max_start и max_start + max_length - 1, если max_length больше нуля, иначе выводим -1, что означает отсутствие фрагмента с суммой элементов, кратной трем.

Демонстрация:
Ввод:
5
1 2 3 4 5

Вывод:
1 3

Совет: При решении этой задачи полезно визуализировать массив и его префиксные суммы. Также стоит проверить свои вычисления на ручных примерах и сравнить их с ожидаемыми значениями.

Ещё задача: Задайте свой собственный массив чисел так, чтобы наибольший непрерывный фрагмент с суммой элементов, кратной трем, был найден. Введите входные данные.