Сумма, делящаяся на три
Необходимо найти самый большой непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3.
Входные данные
В первой строке входных данных содержится число N≤100000. Во второй строке даны N чисел, по модулю не превосходящих 109, — элементы массива.
Выходные данные
Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, то выведите фрагмент с минимальным индексом начала.
Если ответа не существует, то выведите единственное число −1.
Примеры
Ввод
5
Вывод
1 2 3 4 5
1 5
Ввод
4
1 2 3 4
Вывод
1 3
#include
#include
using namespace std;
int main () {
int n;
cin >> n;
vector a(n),s(3, -1), e(3, -1);
for (int i = 0; i < n; i++)
cin >> a[i];
int mmax = -1;
int maxlen = 0;
int m = 0;
int p = 0;
for (int i = 0; i < n; i++) {
if (s[m] < 0)
s[m] = i;
p += a[i] % 3;
m = p % 3;
if (s[m] >= 0) {
e[m] = i;
if (e[m] - s[m] + 1 > maxlen) {
maxlen = e[m] - s[m] + 1;
mmax = m;
}
}
}
if (mmax >= 0)
cout << s[mmax] + 1 << " " << e[mmax] + 1;
else
cout << mmax;
}
233
299
Ответы на вопрос:
Для 256 цветов необходима глубина цвета 8 бит или 1 байт, значит минимальный объем памяти = 256*256 = 65536 байт = 64 кбайт ответ: 64 кбайт
Популярно: Информатика
-
Huuur21.05.2021 19:52
-
satvika6122.07.2021 17:00
-
Андрей348215.01.2023 03:11
-
Diana1727383912.02.2023 11:17
-
морол26.06.2022 18:25
-
котенок13402.01.2021 13:26
-
MAXIM360006.07.2020 00:40
-
nurbibisaidova313.12.2022 12:40
-
зюзя2403.05.2020 13:51
-
2407arinka15.10.2021 20:21