Editing 3748 - Secvente5

Se consideră un șir cu <code>N</code> 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 <code>2</code>
* N-secvență = secvență a cărei sumă este divizibilă cu <code>N</code> (secvența poate fi și banală)
* N-secvență nebanală = secvență nebanală a cărei sumă este divizibilă cu <code>N</code>.

= Cerințe =
Scrieți un program care să citească numărul natural <code>N</code> și apoi șirul de <code>N</code> 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 <code>input.txt</code> conține pe prima linie numere naturale <code>C</code> și <code>N</code> separate printr-un singur spațiu. <code>C</code> reprezentând cerința care trebuie rezolvată (<code>1</code>, <code>2</code> sau <code>3</code>).

= Date de ieșire =
Fișierul <code>output.txt</code> va conține pe prima linie un număr natural reprezentând:

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

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>

== 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 <code>1</code>. Șirul are <code>N=10</code> elemente întregi: <code>-9, -3, 4, -10, -1, -16, 18, 18, -10, 50</code>.

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

== 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 <code>2</code>. Șirul are <code>N=10</code> elemente întregi: <code>-9, -3, 4, -10, -1, -16, 18, 18, -10, 50</code>.

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

== 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 <code>3</code>. Șirul are <code>N=10</code> elemente întregi: <code>-9, -3, 4, -10, -1, -16, 18, 18, -10, 50</code>.

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

== Exemplul 4 ==
input.txt:

3 999999999999

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

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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")

</syntaxhighlight>