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

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