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

Algoritmul, pas cu pas

Pasul cheie — raza maximă a fiecărui centru.

Cu programare dinamică, pentru fiecare celulă calculez câte celule nenule consecutive (incluzând-o) sunt în sus, jos, stânga, dreapta:
- sus[i][j] = sus[i-1][j] + 1 dacă celula e nenulă (altfel $0$ ); analog pentru celelalte direcții.
Raza maximă a crucii din $(i, j)$ e $\min(\text{sus}, \text{jos}, \text{stânga}, \text{dreapta}) - 1$ (pentru o celulă nenulă).

Cerința 1. Număr centrele cu raza maximă egală cu $0$ .

Cerința 2. Maximul razelor maxime.

Cerința 3. Cu sume prefix pe fiecare linie (rowP) și pe fiecare coloană (colP), importanța crucii de rază $R$ din $(i, j)$ e: $S = a_{ij} + (\text{braț stânga}) + (\text{braț dreapta}) + (\text{braț sus}) + (\text{braț jos})$ fiecare braț fiind o sumă pe interval calculată în $O(1)$ . Aleg maximul cu departajările cerute.

Complexitate: $O(N \cdot M)$ — toate cele $4$ tablouri de lungimi și sumele prefix se calculează liniar.

Soluția în C++

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

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

int main() {
    int C, N, M;
    fin >> C >> N >> M;
    vector<vector<int>> a(N + 2, vector<int>(M + 2, 0));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) fin >> a[i][j];

    // Raza maximă a crucii pentru fiecare centru nenul
    vector<vector<int>> maxR(N + 2, vector<int>(M + 2, -1));
    {
        vector<vector<int>> sus(N + 2, vector<int>(M + 2, 0)), jos(N + 2, vector<int>(M + 2, 0)),
            stg(N + 2, vector<int>(M + 2, 0)), drp(N + 2, vector<int>(M + 2, 0));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (a[i][j]) { sus[i][j] = sus[i - 1][j] + 1; stg[i][j] = stg[i][j - 1] + 1; }
        for (int i = N; i >= 1; i--)
            for (int j = M; j >= 1; j--)
                if (a[i][j]) { jos[i][j] = jos[i + 1][j] + 1; drp[i][j] = drp[i][j + 1] + 1; }
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (a[i][j])
                    maxR[i][j] = min(min(sus[i][j], jos[i][j]), min(stg[i][j], drp[i][j])) - 1;
    }

    if (C == 1) {
        long long cnt = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (maxR[i][j] == 0) cnt++;
        fout << cnt << "\n";
    } else if (C == 2) {
        int best = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (maxR[i][j] > best) best = maxR[i][j];
        fout << best << "\n";
    } else { // C == 3
        vector<vector<long long>> rowP(N + 2, vector<long long>(M + 2, 0));
        vector<vector<long long>> colP(N + 2, vector<long long>(M + 2, 0));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) rowP[i][j] = rowP[i][j - 1] + a[i][j];
        for (int j = 1; j <= M; j++)
            for (int i = 1; i <= N; i++) colP[i][j] = colP[i - 1][j] + a[i][j];

        long long bestS = -1;
        int bestR = -1, bi = 0, bj = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) {
                if (maxR[i][j] < 0) continue;
                int R = maxR[i][j];
                long long s = a[i][j];
                s += rowP[i][j - 1] - rowP[i][j - 1 - R]; // braț stânga
                s += rowP[i][j + R] - rowP[i][j];         // braț dreapta
                s += colP[i - 1][j] - colP[i - 1 - R][j]; // braț sus
                s += colP[i + R][j] - colP[i][j];         // braț jos
                // departajare: S desc, R desc, apoi i, j minim (ordinea parcurgerii)
                if (s > bestS || (s == bestS && R > bestR)) {
                    bestS = s; bestR = R; bi = i; bj = j;
                }
            }
        fout << bestS << " " << bi << " " << bj << "\n";
    }
    return 0;
}

Greșeli frecvente

Extinzi brațele pas cu pas pentru fiecare centru — în cel mai rău caz devine $O(N \cdot M \cdot \min(N, M))$ și depășește timpul; precalculează lungimile cu programare dinamică.
Confunzi „rază 0” cu „celulă nenulă” — la cerința 1 numeri doar centrele a căror rază maximă e fix $0$ ; o celulă cu rază $\ge 1$ nu se numără.
Greșești departajarea la cerința 3 — la importanțe egale alegi raza mai mare, apoi $i$ minim, apoi $j$ minim; parcurgerea în ordine + actualizarea doar pe strict mai bun respectă regula.

Algoritmul, pas cu pas

Pasul cheie — raza maximă a fiecărui centru.

Cu programare dinamică, pentru fiecare celulă calculez câte celule nenule consecutive (incluzând-o) sunt în sus, jos, stânga, dreapta:

sus[i][j] = sus[i-1][j] + 1 dacă celula e nenulă (altfel $0$ ); analog pentru celelalte direcții.

Raza maximă a crucii din

(i, j)

\min(\text{sus}, \text{jos}, \text{stânga}, \text{dreapta}) - 1

(pentru o celulă nenulă).

Cerința 1. Număr centrele cu raza maximă egală cu

0

Cerința 2. Maximul razelor maxime.

Cerința 3. Cu sume prefix pe fiecare linie (rowP) și pe fiecare coloană (colP), importanța crucii de rază

R

din

(i, j)

S = a_{ij} + (\text{braț stânga}) + (\text{braț dreapta}) + (\text{braț sus}) + (\text{braț jos})

fiecare braț fiind o sumă pe interval calculată în

O(1)

. Aleg maximul cu departajările cerute.

Complexitate:

O(N \cdot M)

— toate cele

4

tablouri de lungimi și sumele prefix se calculează liniar.

Soluția în C++

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

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

int main() {
    int C, N, M;
    fin >> C >> N >> M;
    vector<vector<int>> a(N + 2, vector<int>(M + 2, 0));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) fin >> a[i][j];

    // Raza maximă a crucii pentru fiecare centru nenul
    vector<vector<int>> maxR(N + 2, vector<int>(M + 2, -1));
    {
        vector<vector<int>> sus(N + 2, vector<int>(M + 2, 0)), jos(N + 2, vector<int>(M + 2, 0)),
            stg(N + 2, vector<int>(M + 2, 0)), drp(N + 2, vector<int>(M + 2, 0));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (a[i][j]) { sus[i][j] = sus[i - 1][j] + 1; stg[i][j] = stg[i][j - 1] + 1; }
        for (int i = N; i >= 1; i--)
            for (int j = M; j >= 1; j--)
                if (a[i][j]) { jos[i][j] = jos[i + 1][j] + 1; drp[i][j] = drp[i][j + 1] + 1; }
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (a[i][j])
                    maxR[i][j] = min(min(sus[i][j], jos[i][j]), min(stg[i][j], drp[i][j])) - 1;
    }

    if (C == 1) {
        long long cnt = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (maxR[i][j] == 0) cnt++;
        fout << cnt << "\n";
    } else if (C == 2) {
        int best = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (maxR[i][j] > best) best = maxR[i][j];
        fout << best << "\n";
    } else { // C == 3
        vector<vector<long long>> rowP(N + 2, vector<long long>(M + 2, 0));
        vector<vector<long long>> colP(N + 2, vector<long long>(M + 2, 0));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) rowP[i][j] = rowP[i][j - 1] + a[i][j];
        for (int j = 1; j <= M; j++)
            for (int i = 1; i <= N; i++) colP[i][j] = colP[i - 1][j] + a[i][j];

        long long bestS = -1;
        int bestR = -1, bi = 0, bj = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) {
                if (maxR[i][j] < 0) continue;
                int R = maxR[i][j];
                long long s = a[i][j];
                s += rowP[i][j - 1] - rowP[i][j - 1 - R]; // braț stânga
                s += rowP[i][j + R] - rowP[i][j];         // braț dreapta
                s += colP[i - 1][j] - colP[i - 1 - R][j]; // braț sus
                s += colP[i + R][j] - colP[i][j];         // braț jos
                // departajare: S desc, R desc, apoi i, j minim (ordinea parcurgerii)
                if (s > bestS || (s == bestS && R > bestR)) {
                    bestS = s; bestR = R; bi = i; bj = j;
                }
            }
        fout << bestS << " " << bi << " " << bj << "\n";
    }
    return 0;
}

Greșeli frecvente

Extinzi brațele pas cu pas pentru fiecare centru — în cel mai rău caz devine $O(N \cdot M \cdot \min(N, M))$ și depășește timpul; precalculează lungimile cu programare dinamică.
Confunzi „rază 0” cu „celulă nenulă” — la cerința 1 numeri doar centrele a căror rază maximă e fix $0$ ; o celulă cu rază $\ge 1$ nu se numără.
Greșești departajarea la cerința 3 — la importanțe egale alegi raza mai mare, apoi $i$ minim, apoi $j$ minim; parcurgerea în ordine + actualizarea doar pe strict mai bun respectă regula.

bonsai

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

bonsai

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++