Problema Numere – OJI 2005, Clasa a 9-a

• Dificultate:
• Autor: Doru Popescu Anastasiu
• Online: InfoArena, PbInfo

Rezumat

Avem o matrice cu $n$ linii și $n$ coloane, care inițial conține toate numerele de la $1$ la $n^2$ Se șterg $n$ valori consecutive din matrice (se înlocuiesc cu $0$ Se cere să se determine cel mai mic și cel mai mare număr din secvența de numere consecutive șterse.

Soluție

Se citește fiecare număr din matrice în variabila $x$ pentru că nu este nevoie să reținem toată matricea. La fiecare pas, se marchează în vectorul caracteristic $\mathrm{frq}$ faptul că numărul $x$ nu a fost șters din matrice. Nu e nevoie să tratăm separat cazul în care $n$ este $0$ pentru că $0$ oricum nu face parte din intervalul dat. La final, facem două parcurgeri ale vectorului caracteristic. Cu prima ne oprim când găsim primul număr șters din matrice, și îl afișăm. Pe a doua parcurgere o facem în sens invers și ne oprim când găsim ultimul număr șters, după care îl afișăm.

Sursă C++

#include <fstream>
#define FMAX 250010

std::ifstream fin("numere.in");
std::ofstream fout("numere.out");

int n;
bool frq[FMAX];

int main() {
    int i, x;

    fin >> n;
    for (i = 0; i < n * n; i++) {
        fin >> x;
        frq[x] = true;
    }

    for (i = 1; i <= n * n; i++)
        if (!frq[i]) {
            fout << i << ' ';
            break;
        }

    for (i = n * n; i >= 1; i--)
        if (!frq[i]) {
            fout << i << '\n';
            break;
        }
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema Numere, lasă un comentariu și te voi ajuta