3709 - tri

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>