Сумма, делящаяся на три
Необходимо найти самый большой непрерывный фрагмент в массиве 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;
}
uses crt;
const n=20;
var i,cp1,cn1:integer;
p,cp,cn:real;
z:array[1..n] of integer;
begin
randomize;
for i:=1 to n do
begin
z[i]:=random(20,-20);
if z[i]>=0 then
begin
cp:=cp+z[i];
cp1:=cp1+1;
end
else
begin
cn:=cp+z[i];
cn1:=cn1+1;
end;
cp:=cp/cp1;
cn:=cn/cn1;
end;
if cp>cn then
p:=cp+cn
else
p:=cp*cn;
for i:=1 to n do
write(z[i],' ');
writeln(#13#10,cp:5:2,' ',cn:5:2,' ',p:5:2);
end.
2.
uses crt;
const n=15;m=4;
var i,j,k,flag,count:integer;
a:array[1..n,1..m] of integer;
temp:array[1..100] of integer;
b:array[1..100,1..m] of integer;
begin
randomize;
k:=1;
count:=0;
for i:=1 to n do
begin
flag:=1;
for j:=1 to m do
begin
a[i,j]:=random(51,1);
if (a[i,j]<10) or (a[i,j]>40) then
flag:=0
end;
if flag=1 then
begin
temp[k]:=i;
count:=count+1;
k:=k+1;
end;
end;
for i:=1 to count do
for j:=1 to m do
b[i,j]:=a[temp[i],j];
writeln('Массив A:');
for i:=1 to n do
begin
for j:=1 to m do
write(a[i,j],' ');
write(#13#10);
end;
if count=0 then
writeln('Нет подходящих строк.')
else
begin
writeln(#13#10,'Массив B:');
for i:=1 to count do
begin
for j:=1 to m do
write(b[i,j],' ');
write(#13#10);
end;
end;
end.
const
nmax=100;
var
n,i,j,nn,nz,np,t:integer;
a,an,az,ap:array[1..nmax] of integer;
begin
// формируем массив и выводим его
Write('Количество элементов в массиве: '); Read(n);
for i:=1 to n do begin
a[i]:=Random(11)-5;
Write(a[i],' ')
end;
Writeln;
// разбиваем массив на три подмассива
nn:=0; nz:=0; np:=0;
for i:=1 to n do
if a[i]<0 then begin nn:=nn+1; an[nn]:=a[i] end
else
if a[i]=0 then begin nz:=nz+1; az[nz]:=a[i] end
else begin np:=np+1; ap[np]:=a[i] end;
// сортируем массив с отрицательными элементами по убыванию
for i:=1 to nn-1 do
for j:=1 to nn-1 do
if an[j]<an[j+1] then
begin t:=an[j]; an[j]:=an[j+1]; an[j+1]:=t end;
// сортируем массив с положительными элементами по возрастанию
for i:=1 to np-1 do
for j:=1 to np-1 do
if ap[j]>ap[j+1] then
begin t:=ap[j]; ap[j]:=ap[j+1]; ap[j+1]:=t end;
// формируем новое содержимое массива a
i:=0;
for j:=1 to nz do begin i:=i+1; a[i]:=az[j] end;
for j:=1 to np do begin i:=i+1; a[i]:=ap[j] end;
for j:=1 to nn do begin i:=i+1; a[i]:=an[j] end;
// вывод результата
for i:=1 to n do Write(a[i],' ');
Writeln
end.
Тестовое решение:
Количество элементов в массиве: 15
1 2 5 0 -5 -3 0 0 1 -4 3 -2 -2 0 -5
0 0 0 0 1 1 2 3 5 -2 -2 -3 -4 -5 -5