Rezolvare PBinfo #3748

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ă:

1. numărul de N-secvențe nebanale, din șir;
2. cea mai mare lungime a unei N-secvențe din șir;
3. 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).