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

  • 43
Нужно найти самый длинный непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3. Входные данные В первой строке входного файла задано число N≤100000. Во второй строке входного файла следуют N чисел, модуль которых не превышает 109 — элементы массива. Выходные данные Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, выведите фрагмент с наименьшим начальным индексом. Если ответа не существует, выведите число -1. Примеры Ввод Вывод 4 1 2 3 4 1 3 5 1 2 3 4 5 1 5
Маргарита
41
Данная задача можно решить следующим образом.

Сначала создадим два словаря: dict_1 и dict_2, в которых ключами будут остатки от деления суммы элементов на 3. Значением словаря dict_1 будет список индексов, сумма элементов до которых делится на 3 без остатка, а значением словаря dict_2 будет список индексов, сумма элементов до которых после деления на 3 имеет остаток 1.

Далее идем по элементам массива слева направо и для каждого элемента выполняем следующие действия:

1. Если элемент делится на 3 без остатка, то добавляем его индекс в список значений словаря dict_1 с ключом 0.

2. Если элемент после деления на 3 имеет остаток 1, то добавляем его индекс в список значений словаря dict_2 с ключом 1.

3. Если элемент после деления на 3 имеет остаток 2, то добавляем его индекс в список значений словаря dict_1 с ключом 2.

После обработки всех элементов массива, найдем самый длинный непрерывный фрагмент с суммой элементов, делящихся на 3, используя словарь dict_1 и суммируя элементы с индексами из этого фрагмента.

Если такой фрагмент не найден, будем искать непрерывный фрагмент с суммой элементов, после деления на 3 имеющих остаток 1. Используем для этого словарь dict_2.

Если ни один из фрагментов не найден, выводим число -1.

В результате получим индексы начала и конца найденного фрагмента.

Давайте разберем наш пример:

Число N равно 4. Вторая строка содержит 4 элемента: 1, 2, 3, 4.

Создаем пустые словари dict_1 и dict_2.

Обрабатываем первый элемент 1:
- 1 делится на 3 без остатка, добавляем его индекс (0) в список значений словаря dict_1 с ключом 0.

Обрабатываем второй элемент 2:
- 2 после деления на 3 имеет остаток 2, добавляем его индекс (1) в список значений словаря dict_1 с ключом 2.

Обрабатываем третий элемент 3:
- 3 делится на 3 без остатка, добавляем его индекс (2) в список значений словаря dict_1 с ключом 0.

Обрабатываем четвертый элемент 4:
- 4 после деления на 3 имеет остаток 1, добавляем его индекс (3) в список значений словаря dict_2 с ключом 1.

Результат:
dict_1 = {0: [0, 2], 2: [1]}
dict_2 = {1: [3]}

На этом этапе нам осталось найти самый длинный непрерывный фрагмент с суммой элементов, делящихся на 3. В нашем случае это фрагмент с индексами от 0 до 2, который соответствует последовательности [1, 2, 3].