2273 - Ssplit

Context

Se consideră un șir a[1], a[2], …, a[n] de numere naturale nenule. Pentru doi indici 1 ≤ i < j < n, notăm cu X = a[1] + a[2] + ... + a[i], Y = a[i+1] + a[i+2] + ... + a[j] și Z = a[j+1] + a[j+2] + ... + a[n] .

Cerinţa

Să se determine doi indici i și j astfel încât diferența max(X, Y, Z) - min(X, Y, Z) să fie minimă.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran valorile indicilor i și j. Dacă sunt mai multe soluții, se va afișa aceea pentru care i este minim, iar dacă sunt mai multe soluții cu același i minim, se va afișa aceea cu indicele j minim.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.", iar daca indeplinesc cerintele enuntate se va afisa mesajul Datele de intrare corespund restricțiilor impuse."

Restricţii şi precizări

• 1 ⩽ n ⩽ 200000
• 1 ⩽ a[i] ⩽ 10000

Exemplu 1

Intrare

10
1 3 4 2 1 2 10 5 8 6

Ieșire

6 8

Explicație

i = 6 și j = 8. În acest caz X = 13, Y = 15, Z = 14. Diferența este max(X, Y, Z) - min(X, Y, Z) = 15-13 = 2. Nu există o împărțire pentru care diferența să fie mai mică.

Exemplu 2

Intrare

3
4000 12000 5000

Ieșire

Datele de intrare nu indeplinesc cerintele impuse

Rezolvare

def gaseste_indici_minim_diferenta(arr):
    n = len(arr)
    suma_totala = sum(arr)
    X = 0
    minim_diff = float('inf')  # Inițializăm cu infinit pentru a asigura găsirea unui minim
    rezultat_i = -1
    rezultat_j = -1

    for i in range(1, n - 1):
        X += arr[i - 1]
        Y = suma_totala - X - arr[i]
        Z = suma_totala - Y - X

        max_xyz = max(X, Y, Z)
        min_xyz = min(X, Y, Z)

        diferenta = max_xyz - min_xyz

        if diferenta < minim_diff:
            minim_diff = diferenta
            rezultat_i = i
            rezultat_j = i + 1

    return rezultat_i, rezultat_j


if __name__ == "__main__":
    # Citirea șirului de numere
    n = int(input())

    if not (1 <= n <= 200000):
        print("Datele de intrare nu indeplinesc cerintele impuse")
        exit()

    arr = list(map(int, input().split()))

    if any(not (1 <= x <= 10000) for x in arr):
        print("Datele de intrare nu indeplinesc cerintele impuse")
        exit()

    # Inițializarea rezultatelor cu valori mari
    rezultat_i = n
    rezultat_j = n
    minim_diff = float('inf')  # Inițializăm cu infinit pentru a asigura găsirea unui minim

    # Căutarea tuturor posibilităților și găsirea celei mai bune
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            X = sum(arr[:i])
            Y = sum(arr[i:j])
            Z = sum(arr[j:])

            max_xyz = max(X, Y, Z)
            min_xyz = min(X, Y, Z)

            diferenta = max_xyz - min_xyz

            if diferenta < minim_diff:
                minim_diff = diferenta
                rezultat_i = i
                rezultat_j = j

    # Afișarea mesajului și a rezultatului
    print("Datele de intrare indeplinesc cerintele impuse")
    print(rezultat_i, rezultat_j)