Andrada378: Pagină nouă: == Enunț == Se citește un număr n și apoi n numere naturale. Numim secvență un grup de elemente aflate pe poziții consecutive în șirul citit. Numim tri-secvență o secvență care începe cu un element impar, se termină cu un element impar și care mai conține în interior exact un element impar. Astfel, fiecare tri-secvență include două secvențe maximale formate doar din elemente pare (eventual, fiecare dintre cele două poate fi vidă). Dezechilibrul unei tr...

2024-01-02T23:50:09Z

Pagină nouă: == Enunț == Se citește un număr n și apoi n numere naturale. Numim secvență un grup de elemente aflate pe poziții consecutive în șirul citit. Numim tri-secvență o secvență care începe cu un element impar, se termină cu un element impar și care mai conține în interior exact un element impar. Astfel, fiecare tri-secvență include două secvențe maximale formate doar din elemente pare (eventual, fiecare dintre cele două poate fi vidă). Dezechilibrul unei tr...

New page

== Enunț ==
Se citește un număr n și apoi n numere naturale. Numim secvență un grup de elemente aflate pe poziții consecutive în șirul citit. Numim tri-secvență o secvență care începe cu un element impar, se termină cu un element impar și care mai conține în interior exact un element impar. Astfel, fiecare tri-secvență include două secvențe maximale formate doar din elemente pare (eventual, fiecare dintre cele două poate fi vidă). Dezechilibrul unei tri-secvențe se calculează astfel: determinăm suma elementelor din secvența din stânga formată doar din elemente pare, suma elementelor din secvența din dreapta formată doar din elemente pare și apoi diferența în modul a celor două valori (adică scădem din cea mare pe cea mică). Dacă vreuna dintre cele două secvențe de elemente pare este vidă, aceasta se consideră de sumă 0. Această diferență reprezintă dezechilibrul tri-secvenței.

== Cerința ==
Să se determine o tri-secvența de dezechilibru minim. Dacă sunt mai multe astfel de tri-secvențe, să se determine cea care începe la o poziție cât mai mare.

== Date de intrare ==
Fișierul de intrare triin.txt conține pe prima linie un număr natural n ce reprezintă numărul de elemente ale șirului dat. Pe a doua linie sunt n numere naturale reprezentând elementele șirului, în ordinea crescătoare a pozițiilor, numerotate începând cu 1. În testele de intrare se dă n pe un rând iar elementele șirului pe rândul

următor separate prin câte un spațiu.

== Date de ieșire ==
Fișierul de ieșire tri.out va conține pe prima linie două numere naturale cuprinse între 1 și n (inclusiv), separate printr-un spațiu, reprezentând poziția de început, respectiv cea de final a tri-secvenței determinate.

== Restricții și precizări ==

* 3 ≤ n ≤ 100.000
* 0 ≤ valoarea unui element ≤ 1.000.000.000
* Șirul conține cel puțin 3 elemente impare

== Exemplu: ==
'''triin.txt'''

16

2 3 8 7 4 2 5 10 7 9 8 11 8 2 13 6

'''triout.txt'''

10 15

== Explicație ==
Avem 5 tri-secvențe: 3 8 7 4 2 5, cu dezechilibrul 2; 7 4 2 5 10 7, cu dezechilibrul 4; 5 10 7 9, cu

dezechilibrul 10; 7 9 8 11, cu dezechilibrul 8; 9 8 11 8 2 13, cu dezechilibrul 2

== Rezolvare ==
<syntaxhighlight lang="python">
def validare_intrare(n, arr):
if not (3 <= n <= 100000):
print("Numărul de elemente trebuie să fie între 3 și 100.000.")
return False

if len(arr) != n:
print("Numărul de elemente din șir nu corespunde valorii specificate.")
return False

for x in arr:
if not (0 <= x <= 1000000000):
print("Valorile trebuie să fie între 0 și 1.000.000.000.")
return False

numar_impare = sum(1 for x in arr if x % 2 != 0)
if numar_impare < 3:
print("Șirul trebuie să conțină cel puțin 3 elemente impare.")
return False

return True

def gaseste_pozitii_diferenta_minima(n, arr):
if not validare_intrare(n, arr):
return None

minim = 2000000000
numar_impare = 0
suma_curenta = 0
suma_anterioara = 0
primul = 0
ultimul = 0
poz_impar_anterior_anterior = 0
poz_impar_anterior = 0
diferenta = 0

for i in range(1, n + 1):
x = arr[i - 1]

if x % 2 == 0:
suma_curenta += x
else:
numar_impare += 1

if numar_impare >= 3:
diferenta = suma_curenta - suma_anterioara
diferenta = abs(diferenta)

if diferenta <= minim:
minim = diferenta
primul = poz_impar_anterior_anterior
ultimul = i

poz_impar_anterior_anterior = poz_impar_anterior
poz_impar_anterior = i
suma_anterioara = suma_curenta
suma_curenta = 0

return primul, ultimul

if __name__ == "__main__":

with open("triin.txt", "r") as fin:
n = int(fin.readline())
arr = list(map(int, fin.readline().split()))

rezultat = gaseste_pozitii_diferenta_minima(n, arr)

with open("triout.txt", "w") as fout:
if rezultat:
fout.write(f"{rezultat[0]} {rezultat[1]}\n")
else:
fout.write("Date de intrare invalide\n")
</syntaxhighlight>

3709 - tri - Revision history