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

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