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 ⩽ n ⩽ 200000
• 1 ⩽ a[i] ⩽ 10000

Exemplu 1

Intrare

10

1 3 4 2 1 2 10 5 8 6

Ieșire

6 8

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("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ă.