Enunțul problemei numere, de clasa a 9-a, dată în 2005 la OJI, se găsește pe InfoArena și 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;
        }

    fout.close();
    return 0;
}

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

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!

PayPal