De ce contează?
Numeri cuvintele dintr-o propoziție. Un cuvânt e o secvență de litere — numeri câte secvențe de litere există, nu câte litere sunt în total. Același principiu: detectezi când „pornește" un cuvânt nou (prima literă după spațiu) și incrementezi contorul o singură dată per cuvânt, nu la fiecare literă.
Diferența față de lungimea maximă
| Ce vrei | Ce calculezi |
|---|---|
| Lungimea celui mai lung bloc | lung_max — actualizat la fiecare element din bloc |
| Câte blocuri există | nr_blocuri — incrementat o singură dată la începutul fiecărui bloc |
Algoritmul cu in_bloc
Variabila booleană in_bloc reține dacă suntem activ într-un bloc. Contorul crește doar la tranziția fals→adevărat, nu la fiecare element valid:
Sir: 2 4 3 6 8 1 10 (proprietate: par)
nr_blocuri = 0, in_bloc = false
x=2: par, !in_bloc → nr_blocuri=1, in_bloc=true
x=4: par, in_bloc → nimic (suntem deja in bloc)
x=3: impar → in_bloc=false
x=6: par, !in_bloc → nr_blocuri=2, in_bloc=true
x=8: par, in_bloc → nimic
x=1: impar → in_bloc=false
x=10: par, !in_bloc → nr_blocuri=3, in_bloc=true
Rezultat: 3Implementare C++
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("nr_secv.in");
ofstream fout("nr_secv.out");
int n;
fin >> n;
int nr_blocuri = 0;
bool in_bloc = false;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
if (x % 2 == 0) { // proprietatea: par
if (!in_bloc) {
nr_blocuri++; // inceput de bloc nou
in_bloc = true;
}
} else {
in_bloc = false; // iesire din bloc
}
}
fout << nr_blocuri << "\n";
return 0;
}Exemplu: 7 / 2 4 3 6 8 1 10 → 3
Combinat — număr și lungime maximă simultan
int nr_blocuri = 0, lung_cur = 0, lung_max = 0;
bool in_bloc = false;
for (int i = 0; i < n; i++) {
int x; fin >> x;
if (x % 2 == 0) {
if (!in_bloc) { nr_blocuri++; in_bloc = true; }
lung_cur++;
if (lung_cur > lung_max) lung_max = lung_cur;
} else {
in_bloc = false;
lung_cur = 0;
}
}Tiparul in_bloc e universal: funcționează pentru orice proprietate — valori pozitive, valori în intervalul [a,b], valori divizibile cu k, valori mai mari decât precedenta. Schimbi doar condiția din if, restul codului rămâne identic.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Numărarea blocurilor | O(n) | O(1) |
Greșeala 1: Incrementezi nr_blocuri la fiecare element valid, nu doar la primul. Numeri 4 în loc de 3 pentru 2 4 3 6 8 1 10.
Greșeala 2: Uiți să resetezi in_bloc = false când proprietatea nu e satisfăcută. Blocurile par contopite — un singur bloc mare în loc de mai multe.
Greșeala 3: Confunzi numărarea blocurilor cu numărarea elementelor valide. nr_blocuri ≠ nr_elemente_valide. Prima numără grupuri, a doua numără individual.