Editing 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 &les; '''n''' &les; 200000
* 1 &les; ''' a[i] ''' &les; 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ă.
 
<br>
== Exemplu 2 ==
; Intrare
 3
 4000 12000 5000
; Ieșire
 Datele de intrare nu indeplinesc cerintele impuse

<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
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)

</syntaxhighlight>