Problema mario — OJI 2026, Clasa VII, rezolvare explicată

Algoritmul, pas cu pas

Notez prefixMario[i] și prefixWario[i] energiile consumate până la săritura $i$ , și $D[i] = \text{prefixMario}[i] - \text{prefixWario}[i]$ , cu $D[0] = 0$ .

Cerința 1 — diferența maximă. Parcurg $i$ de la $1$ la $N$ și rețin indicele cu $|D[i]|$ maxim (primul, dacă sunt mai multe).

Cerința 2 — fereastra de lungime $K$ a lui Mario.

Calculez suma primei ferestre $M[1..K]$ .
Glisez fereastra: la mutare, adaug noul element din dreapta și scad pe cel ieșit din stânga (în $O(1)$ ).
Rețin începutul cu suma maximă (la egalitate, cel mai mic).

Cerința 3 — segment cu energii egale.

Energiile pe $(st, dr)$ sunt egale $\iff \text{prefixMario}[dr] - \text{prefixMario}[st-1] = \text{prefixWario}[dr] - \text{prefixWario}[st-1] \iff D[dr] = D[st-1]$ .
Deci caut o valoare care se repetă în șirul $D[0..N]$ .
Țin într-un dicționar prima poziție a fiecărei valori; la o repetare am segmentul $(\text{primaPoz}+1, \text{pozCurentă})$ . Aleg $st$ minim, apoi $dr$ minim.

Complexitate: $O(N)$ pentru cerințele 1 și 2, $O(N)$ în medie pentru cerința 3 (cu dicționar).

Soluția în C++

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

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

int main() {
    int C, N, K;
    fin >> C >> N >> K;
    vector<long long> M(N + 1), W(N + 1), pM(N + 1, 0), pW(N + 1, 0);
    for (int i = 1; i <= N; i++) fin >> M[i];
    for (int i = 1; i <= N; i++) fin >> W[i];
    for (int i = 1; i <= N; i++) {
        pM[i] = pM[i - 1] + M[i];
        pW[i] = pW[i - 1] + W[i];
    }

    if (C == 1) {
        long long best = -1;
        int bi = 0;
        for (int i = 1; i <= N; i++) {
            long long d = pM[i] - pW[i];
            if (d < 0) d = -d;
            if (d > best) { best = d; bi = i; }
        }
        fout << bi << "\n";

    } else if (C == 2) {
        long long s = 0;
        for (int i = 1; i <= K; i++) s += M[i]; // prima fereastră
        long long best = s;
        int bi = 1;
        for (int i = 2; i + K - 1 <= N; i++) {
            s += M[i + K - 1] - M[i - 1]; // glisăm fereastra în O(1)
            if (s > best) { best = s; bi = i; }
        }
        fout << bi << "\n";

    } else { // C == 3
        unordered_map<long long, int> prima; // valoare D -> prima poziție
        int bst = -1, bdr = -1;
        for (int r = 0; r <= N; r++) {
            long long d = pM[r] - pW[r];
            auto it = prima.find(d);
            if (it != prima.end()) {
                int st = it->second + 1, dr = r;
                if (bst == -1 || st < bst || (st == bst && dr < bdr)) { bst = st; bdr = dr; }
            } else {
                prima[d] = r;
            }
        }
        if (bst == -1) fout << "-1 -1\n";
        else fout << bst << " " << bdr << "\n";
    }
    return 0;
}

Greșeli frecvente

Calculezi diferența pe săritură, nu pe prefix — cerința 1 cere diferența energiei totale (cumulate) până la acel obstacol, deci $|D[i]|$ cu $D$ sume prefix, nu $|M_i - W_i|$ .
Recalculezi fereastra de la zero — cu $N$ până la $10^6$ , recalcularea sumei fiecărei ferestre dă $O(N \cdot K)$ ; glisează în $O(1)$ .
Uiți $D[0] = 0$ la cerința 3 — un segment care începe de la prima săritură corespunde valorii $D[0]$ ; dacă nu pui poziția $0$ în dicționar, pierzi astfel de segmente.

Algoritmul, pas cu pas

Notez prefixMario[i] și prefixWario[i] energiile consumate până la săritura

i

, și

D[i] = \text{prefixMario}[i] - \text{prefixWario}[i]

, cu

D[0] = 0

Cerința 1 — diferența maximă. Parcurg

i

de la

1

N

și rețin indicele cu

|D[i]|

maxim (primul, dacă sunt mai multe).

Cerința 2 — fereastra de lungime $K$ a lui Mario.

Calculez suma primei ferestre

M[1..K]

Glisez fereastra: la mutare, adaug noul element din dreapta și scad pe cel ieșit din stânga (în

O(1)

Rețin începutul cu suma maximă (la egalitate, cel mai mic).

Cerința 3 — segment cu energii egale.

Energiile pe

(st, dr)

sunt egale

\iff \text{prefixMario}[dr] - \text{prefixMario}[st-1] = \text{prefixWario}[dr] - \text{prefixWario}[st-1] \iff D[dr] = D[st-1]

Deci caut o valoare care se repetă în șirul

D[0..N]

Țin într-un dicționar prima poziție a fiecărei valori; la o repetare am segmentul

(\text{primaPoz}+1, \text{pozCurentă})

. Aleg

st

minim, apoi

dr

minim.

Complexitate:

O(N)

pentru cerințele 1 și 2,

O(N)

în medie pentru cerința 3 (cu dicționar).

Soluția în C++

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

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

int main() {
    int C, N, K;
    fin >> C >> N >> K;
    vector<long long> M(N + 1), W(N + 1), pM(N + 1, 0), pW(N + 1, 0);
    for (int i = 1; i <= N; i++) fin >> M[i];
    for (int i = 1; i <= N; i++) fin >> W[i];
    for (int i = 1; i <= N; i++) {
        pM[i] = pM[i - 1] + M[i];
        pW[i] = pW[i - 1] + W[i];
    }

    if (C == 1) {
        long long best = -1;
        int bi = 0;
        for (int i = 1; i <= N; i++) {
            long long d = pM[i] - pW[i];
            if (d < 0) d = -d;
            if (d > best) { best = d; bi = i; }
        }
        fout << bi << "\n";

    } else if (C == 2) {
        long long s = 0;
        for (int i = 1; i <= K; i++) s += M[i]; // prima fereastră
        long long best = s;
        int bi = 1;
        for (int i = 2; i + K - 1 <= N; i++) {
            s += M[i + K - 1] - M[i - 1]; // glisăm fereastra în O(1)
            if (s > best) { best = s; bi = i; }
        }
        fout << bi << "\n";

    } else { // C == 3
        unordered_map<long long, int> prima; // valoare D -> prima poziție
        int bst = -1, bdr = -1;
        for (int r = 0; r <= N; r++) {
            long long d = pM[r] - pW[r];
            auto it = prima.find(d);
            if (it != prima.end()) {
                int st = it->second + 1, dr = r;
                if (bst == -1 || st < bst || (st == bst && dr < bdr)) { bst = st; bdr = dr; }
            } else {
                prima[d] = r;
            }
        }
        if (bst == -1) fout << "-1 -1\n";
        else fout << bst << " " << bdr << "\n";
    }
    return 0;
}

Greșeli frecvente

Calculezi diferența pe săritură, nu pe prefix — cerința 1 cere diferența energiei totale (cumulate) până la acel obstacol, deci $|D[i]|$ cu $D$ sume prefix, nu $|M_i - W_i|$ .
Recalculezi fereastra de la zero — cu $N$ până la $10^6$ , recalcularea sumei fiecărei ferestre dă $O(N \cdot K)$ ; glisează în $O(1)$ .
Uiți $D[0] = 0$ la cerința 3 — un segment care începe de la prima săritură corespunde valorii $D[0]$ ; dacă nu pui poziția $0$ în dicționar, pierzi astfel de segmente.

mario

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

mario

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++