Miawinator: Pagină nouă: 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 b...

2024-01-05T02:34:52Z

Pagină nouă: 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 b...

New page

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>

3748 - Secvente5 - Revision history