Problema zudt — OJI 2026, Clasa VI, rezolvare explicată

Algoritmul, pas cu pas

Cheia tuturor cerințelor sunt sumele prefix: $P[k] = a_1 + a_2 + \dots + a_k$ , cu $P[0] = 0$ . Atunci $S(i, j) = P[j] - P[i-1]$ și suma totală e $\text{Total} = P[N]$ .

Cerința 1 — punct de echilibru. $S(1, i) = S(i+1, N)$ devine $P[i] = \text{Total} - P[i]$ . Parcurg $i$ de la $1$ la $N-1$ și caut prima poziție unde egalitatea ține.

Cerința 2 — sărim elementul $a_i$ . $S(1, i-1) = S(i+1, N)$ devine $P[i-1] = \text{Total} - P[i]$ . Parcurg $i$ de la $2$ la $N-1$ .

Cerința 3 — trei bucăți egale, sărind $a_i$ și $a_j$ .

Condiția e $P[i-1] = P[j-1] - P[i] = \text{Total} - P[j]$ .
Pentru fiecare $i$ , partea stângă e $P[i-1]$ . Ca partea dreaptă să fie egală, am nevoie de $P[j] = \text{Total} - P[i-1]$ .
Cum prefixele cresc strict (toate $a_i \ge 1$ ), există cel mult un singur $j$ cu acea valoare — îl găsesc prin căutare binară.
Verific apoi că bucata din mijloc $P[j-1] - P[i]$ e egală cu $P[i-1]$ și că $i+1 < j < N$ . Returnez prima pereche găsită.

Complexitate: $O(N)$ pentru cerințele 1 și 2, $O(N \log N)$ pentru cerința 3.

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("zudt.in");
ofstream fout("zudt.out");

int main() {
    int C, N;
    fin >> C >> N;
    vector<long long> P(N + 1, 0);
    for (int k = 1; k <= N; k++) {
        long long x;
        fin >> x;
        P[k] = P[k - 1] + x; // sume prefix
    }
    long long Total = P[N];

    if (C == 1) {
        int ans = 0;
        for (int i = 1; i < N && ans == 0; i++)
            if (P[i] == Total - P[i]) ans = i;
        fout << ans << "\n";

    } else if (C == 2) {
        int ans = 0;
        for (int i = 2; i < N && ans == 0; i++)
            if (P[i - 1] == Total - P[i]) ans = i;
        fout << ans << "\n";

    } else { // C == 3
        int fi = 0, fj = 0;
        for (int i = 2; i <= N && fi == 0; i++) {
            long long left = P[i - 1];
            long long want = Total - left; // căutăm j cu P[j] = want
            int lo = 1, hi = N, j = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (P[mid] == want) { j = mid; break; }
                else if (P[mid] < want) lo = mid + 1;
                else hi = mid - 1;
            }
            // i+1 < j < N și bucata din mijloc egală cu left
            if (j != -1 && i + 1 < j && j < N && P[j - 1] - P[i] == left) {
                fi = i;
                fj = j;
            }
        }
        if (fi == 0) fout << 0 << "\n";
        else fout << fi << " " << fj << "\n";
    }
    return 0;
}

Greșeli frecvente

Recalculezi sumele pentru fiecare poziție — cu $N$ până la $200\,000$ asta dă $O(N^2)$ și depășește timpul; folosește sume prefix și răspunde în $O(1)$ pe poziție.
Folosești int pentru sume — suma poate atinge $200\,000 \cdot 1\,000 = 2 \cdot 10^8$ , care încape în int, dar la cerința 3 e mai sigur long long; oricum, fii atent la tip.
Greșești marginile la cerința 3 — trebuie $1 < i$ și $i+1 < j < N$ ; dacă lași $j = i+1$ sau $j = N$ obții bucăți goale sau ieși din șir.

Algoritmul, pas cu pas

Cheia tuturor cerințelor sunt sumele prefix:

P[k] = a_1 + a_2 + \dots + a_k

, cu

P[0] = 0

. Atunci

S(i, j) = P[j] - P[i-1]

și suma totală e

\text{Total} = P[N]

Cerința 1 — punct de echilibru.

S(1, i) = S(i+1, N)

devine

P[i] = \text{Total} - P[i]

. Parcurg

i

de la

1

N-1

și caut prima poziție unde egalitatea ține.

Cerința 2 — sărim elementul $a_i$ .

S(1, i-1) = S(i+1, N)

devine

P[i-1] = \text{Total} - P[i]

. Parcurg

i

de la

2

N-1

Cerința 3 — trei bucăți egale, sărind $a_i$ și $a_j$ .

Condiția e

P[i-1] = P[j-1] - P[i] = \text{Total} - P[j]

Pentru fiecare

i

, partea stângă e

P[i-1]

. Ca partea dreaptă să fie egală, am nevoie de

P[j] = \text{Total} - P[i-1]

Cum prefixele cresc strict (toate

a_i \ge 1

), există cel mult un singur

j

cu acea valoare — îl găsesc prin căutare binară.

Verific apoi că bucata din mijloc

P[j-1] - P[i]

e egală cu

P[i-1]

și că

i+1 < j < N

. Returnez prima pereche găsită.

Complexitate:

O(N)

pentru cerințele 1 și 2,

O(N \log N)

pentru cerința 3.

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("zudt.in");
ofstream fout("zudt.out");

int main() {
    int C, N;
    fin >> C >> N;
    vector<long long> P(N + 1, 0);
    for (int k = 1; k <= N; k++) {
        long long x;
        fin >> x;
        P[k] = P[k - 1] + x; // sume prefix
    }
    long long Total = P[N];

    if (C == 1) {
        int ans = 0;
        for (int i = 1; i < N && ans == 0; i++)
            if (P[i] == Total - P[i]) ans = i;
        fout << ans << "\n";

    } else if (C == 2) {
        int ans = 0;
        for (int i = 2; i < N && ans == 0; i++)
            if (P[i - 1] == Total - P[i]) ans = i;
        fout << ans << "\n";

    } else { // C == 3
        int fi = 0, fj = 0;
        for (int i = 2; i <= N && fi == 0; i++) {
            long long left = P[i - 1];
            long long want = Total - left; // căutăm j cu P[j] = want
            int lo = 1, hi = N, j = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (P[mid] == want) { j = mid; break; }
                else if (P[mid] < want) lo = mid + 1;
                else hi = mid - 1;
            }
            // i+1 < j < N și bucata din mijloc egală cu left
            if (j != -1 && i + 1 < j && j < N && P[j - 1] - P[i] == left) {
                fi = i;
                fj = j;
            }
        }
        if (fi == 0) fout << 0 << "\n";
        else fout << fi << " " << fj << "\n";
    }
    return 0;
}

Greșeli frecvente

Recalculezi sumele pentru fiecare poziție — cu $N$ până la $200\,000$ asta dă $O(N^2)$ și depășește timpul; folosește sume prefix și răspunde în $O(1)$ pe poziție.
Folosești int pentru sume — suma poate atinge $200\,000 \cdot 1\,000 = 2 \cdot 10^8$ , care încape în int, dar la cerința 3 e mai sigur long long; oricum, fii atent la tip.
Greșești marginile la cerința 3 — trebuie $1 < i$ și $i+1 < j < N$ ; dacă lași $j = i+1$ sau $j = N$ obții bucăți goale sau ieși din șir.

zudt

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

zudt

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++