Сумма, делящаяся на три Необходимо найти самый большой непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3. Входные данные В первой строке входного файла содержится число N≤100000. Во второй строке входного файла следуют N чисел, по модулю не превосходящих 109 — элементы массива. Выходные данные Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, то выведите фрагмент с минимальным индексом начала. Если ответа не существует, то выведите единственное число −1. Примеры Ввод Вывод 4 1 2 3 4 1 3 5 1 2 3 4 5 1 5 Решите на c++
Рассмотрим первый вариант, когда символ Х стоит на последнем месте:
Всего 5 позиций. Последняя из них точно будет занята символом Х, тогда свободными остаются первые 4 позиции: * * * * Х
На каждую из них может приходиться какой-то один из символов А, В или С
Тогда общее число возможных вариантов вычисляется, как 3^4 = 81.
Рассмотрим второй вариант, когда символа Х нет вовсе. В этом случае на каждую из 5-ти позиции может приходиться один из символов А, В или С.
Тогда общее число вариантов вычисляется, как 3^5 = 243
В итоге получаем, что всего кодовых слов может быть 243+81 = 324.