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 indeplinesc cerintele impuse.".
== Restricţii şi precizări ==
* 1 &les; '''n''' &les; 200000
* 1 &les; ''' a[i] ''' &les; 200000
== Exemplu 1 ==
; Intrare
:10
:1 3 4 2 1 2 10 5 8 6

; Ieșire
: 6 8 
<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("Introduceți numărul n: "))

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

    arr = list(map(int, input(f"Introduceți {n} numere separate prin spațiu: ").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 rezultatului
    print(f"Indicii i și j sunt: {rezultat_i} și {rezultat_j}")

</syntaxhighlight>
==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ă.