3748 - Secvente5

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 input.txt 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 output.txt 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

Exemplul 1

input.txt:

1 10

-9 -3 4 -10 -1 -16 18 18 -10 50

output.txt:

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

input.txt:

2 10

9 -3 4 -10 -1 -16 18 18 -10 50

output.txt:

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

input.txt:

3 10

9 -3 4 -10 -1 -16 18 18 -10 50

output.txt:

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).

Exemplul 4

input.txt:

3 999999999999

-9 -3 4 -10 -1 -16 18 18 -10 50

Output:

Input-ul nu convine conditiilor

Rezolvare

def verificare(n):
    if not(2<=n<=100000):
        print("Input-ul nu convine conditiilor")
        exit()

with open("input.txt", "r") as f, open("output.txt", "w") as g:
    C, N = map(int, f.readline().split())
    verificare(N)
    v = [0] * 100001
    prim = [0] * 100001
    ult = [0] * 100001
    s = [0] * 100001
    rest = [0] * 100001
    nrv = 0
    nrs = 0
    i = 0
    sc = 0
    r = 0
    smax = 0
    lgmax = 0
    lg = 0
    srest = [0] * 100001
    sumaseccurenta = 0

    l=list(map(int, f.readline().split()))

    for i in range(1, N + 1):
        x = l[i-1]
        if x % N == 0:
            nrv += 1
            smax = max(smax, x)
        s[i] = s[i - 1] + x
        r = s[i] % N
        if r == 0:
            smax = max(smax, s[i])
            lgmax = max(lgmax, i)
        if r < 0:
            r = N + r
        rest[r] += 1
        if prim[r] == 0:
            ult[r] = prim[r] = i
        ult[r] = i
        lg = i - prim[r]
        if lg > 1 and lg > lgmax:
            lgmax = lg
        if rest[r] == 1:
            srest[r] = s[i]
        else:
            if s[i] < srest[r]:
                srest[r] = s[i]
            smax = max(smax, s[i] - srest[r])  # suma N-secventei curecte este s[i]-srest[r]

    nrs = rest[0]
    for i in range(N):
        nrs = nrs + rest[i] * (rest[i] - 1) // 2
    nrs = nrs - nrv

    if C == 1:
        g.write(str(nrs) + "\n")
    elif C == 2:
        g.write(str(lgmax) + "\n")
    else:
        g.write(str(smax) + "\n")