# PBinfo #2273 – ssplit – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

Restricții și precizări

1 ≤ n ≤ 200 000
1 ≤ a[i] ≤ 10 000

Exemplu:
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ă.

## Cod sursă C++

```cpp
/**
   Complexitate O(n x n)
*/
#include <bits/stdc++.h>
#define nmax 200005
#define oo 2000000001
using namespace std;
int a[nmax], n;
inline int Min(int x, int y, int z)
{
    return min(min(x, y), z);
}
inline int Max(int x, int y, int z)
{
    return max(max(x, y), z);
}
int main()
{
    int i, j, difmin, P, Q, X, Y, Z, d;
    /// citire
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    /// sume partiale
    for (i = 2; i <= n; i++)
        a[i] += a[i - 1];
    /// pentru fiecare i=1..n-2 caut liniar pozitia lui j
    P = 1; Q = 2;
    X = a[1]; Y = a[2] - a[1]; Z = a[n] - a[2];
    difmin = Max(X, Y, Z) - Min(X, Y, Z);
    for (i = 1; i <= n - 2; i++)
        for (j = i + 1; j < n; j++)
        {
            X = a[i];
            Y = a[j] - a[i];
            Z = a[n] - a[j];
            d = Max(X, Y, Z) - Min(X, Y, Z);
            if (d < difmin)
            {
                difmin = d;
                P = i; Q= j;
            }
        }
    /// afisare
    cout << P << " " << Q << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2273)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2273/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2273/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)