Problema Numere – OJI 2005, Clasa a 9-a

Problema Numere – OJI 2005, Clasa a 9-a

Rezumat

Avem o matrice cu nn linii și nn coloane, care inițial conține toate numerele de la 11 la n2n^2 Se șterg nn valori consecutive din matrice (se înlocuiesc cu 00 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 xx pentru că nu este nevoie să reținem toată matricea. La fiecare pas, se marchează în vectorul caracteristic frq\mathrm{frq} faptul că numărul xx nu a fost șters din matrice. Nu e nevoie să tratăm separat cazul în care nn este 00 pentru că 00 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++

Problema Numere
#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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii