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

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