# PBinfo #3748 – Secvente5 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se consideră un șir cu N elemente numere întregi. Definim următoarele noțiuni:


secvență în șir = elemente situate pe poziții consecutive în șir
lungimea unei secvențe = numărul de elemente care o formează
suma unei secvențe = suma elementelor care o formează
secvența nebanală = secvența de lungime cel puțin egală cu 2
N-secvență =  secvență a cărei sumă este divizibilă cu N (secvența poate fi și banală)
N-secvență nebanală =  secvență nebanală a cărei sumă este divizibilă cu N.

Cerințe
Scrieți un program care să citească numărul natural N  și apoi șirul de N elemente. Programul determină:


numărul de N-secvențe nebanale, din șir;
cea mai mare lungime a unei N-secvențe din șir;
cea mai mare sumă a unei N-secvențe din șir.

Date de intrare
Fișierul de intrare secvente5.in conține pe prima linie numere naturale C și N separate printr-un singur spațiu. C reprezentând cerința care trebuie rezolvată (1, 2 sau 3). 

Date de ieșire
Fișierul secvente5.out va conține pe prima linie un număr natural reprezentând:


dacă C = 1, numărul de N-secvențe nebanale din șir (răspunsul la cerința 1);
dacă C = 2, cea mai mare lungime a unei N-secvențe din șir (răspunsul la cerința 2);
dacă C = 3, cea mai mare sumă a unei N-secvențe din șir (răspunsul la cerința 3).

Restricții și precizări

2 ≤ N ≤ 100.000
elementele șirului sunt numere întregi din interval închis [-109 , 109]
în șirul de numere dat există cel puțin o N-secvență a cărei sumă este un număr natural
numărul întreg negativ X este divizibil cu numărul natural nenul N dacă restul împărțirii  modulului lui X la N este 0 (de exemplu, X=-30 este divizibil cu N=6, iar X=-45 nu este divizibil cu N=6)
Pentru cerințele 1 și 2 se acordă câte 30p, iar pentru cerința 3 se acordă 40p.

Exemplul 1:
secvente5.in

1 10
-9 -3 4 -10 -1 -16 18 18 -10 50
secvente5.out

8
Explicație
Se rezolvă cerința 1. Șirul are N=10 elemente întregi:  -9, -3, 4, -10, -1, -16, 18, 18, -10, 50. 

Cele N-secvențe nebanale sunt (-3, 4, -10, -1), (-16, 18, 18), (-10, 50), (-16, 18, 18, -10), (-16, 18, 18, -10, 50), (-3, 4, -10, -1, -16, 18, 18), (-3, 4, -10, -1, -16, 18, 18, -10), (-3, 4, -10, -1, -16, 18, 18, -10, 50).

Exemplul 2:
secvente5.in

2 10
-9 -3 4 -10 -1 -16 18 18 -10 50
secvente5.out

9
Explicație
Se rezolvă cerința 2. Șirul are N=10 elemente întregi:  -9, -3, 4, -10, -1, -16, 18, 18, -10, 50. 

Cea mai lungă dintre aceste secvențe este N-secvența (-3, 4,-10,-1,-16,18,18,-10,50). Lungimea acestei secvențe este 9.

Exemplul 3:
secvente5.in

3 10
-9 -3 4 -10 -1 -16 18 18 -10 50
secvente5.out

60
Explicație
Se rezolvă cerința 3. Șirul are N=10 elemente întregi:  -9, -3, 4, -10, -1, -16, 18, 18, -10, 50.

Suma maximă a unei secvente este 60 ( suma N-secvenței: -16,18,18,-10,50).

## Cod sursă C++

```cpp
// Stelian Ciurea
#include <fstream>
#define nmax 1000001
using bigint = long long int;
using namespace std;
bigint  v[nmax], first[nmax], last[nmax], ct[nmax], sumpartiala[nmax], sumperest[nmax];
bigint c, n, ctmultipliin, summax;
bool eprima[nmax];
int main()
{
	ifstream in("secvente5.in");
	ofstream out("secvente5.out");
	in >> c>> n;
	for (int i = 1; i <= n; i++)
		in >> v[i];
	int lungmax = -(n + 1), pozmax, lungcrt;
	fill(first, first + n + 10, -1);
	fill(last, last + n + 10, -1);
	bigint sum = 0, restsum;
	first[0] = 0;
	eprima[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		sum = sum + v[i];
		sumpartiala[i] = sum;
		restsum = sum % n;
		if (restsum < 0)
			restsum = restsum + n;
		ct[restsum]++;
		if (first[restsum] < 0)
			first[restsum] = i;
		last[restsum] = i;
		if (v[i] % n == 0)
			ctmultipliin++;
		if (restsum != 0)
			lungcrt = last[restsum] - first[restsum];
		else
			lungcrt = last[restsum];
		if (lungcrt > lungmax)
		{
			lungmax = lungcrt;
			pozmax = restsum;
		}
		bigint sumcrt = sumpartiala[last[restsum]] - sumperest[restsum];
		if (eprima[restsum] == 0)
		{
			eprima[restsum] = 1;
			sumperest[restsum] = sumcrt;
		}
		else
		{
			if (sumcrt < 0)
				sumperest[restsum] = sumpartiala[last[restsum]];
			if (sumcrt > summax)
				summax = sumcrt;
		}
	}
	bigint nrsecvente = 0;
	for (int i = 0; i < n; i++)
		nrsecvente += (ct[i] * (ct[i] - 1) / 2);
	nrsecvente += ct[0] - ctmultipliin;
	if (c == 2)
	{
		out << lungmax << endl;
	}
	if (c == 1)
	{
		out << nrsecvente << endl;
	}
	if (c == 3)
	{
		out << summax << endl;
	}
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3748)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3748/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3748/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)