Dat je niz koji sadrži brojeve 0 i 1. Operacija brisanja podrazumeva pronalaženje prve grupe od \(k_1\) uzastopnih pojavljivanja cifre 0 ili \(k_2\) uzastopnih pojavljivanja cifre 1, a zatim brisanje pomenute grupe. Ispisati niz koji se dobija primenom pomenute operacije brisanja sve dok je to moguće.
Sa standardnog ulaza unose se prirodni brojevi \(n\) (\(1 \leq n \leq 10^6\)), \(k_1\) i \(k_2\) (\(3 \leq k_1, k_2 \leq 5\)). Nakon toga se u novom redu unosi niz binarnih cifara dužine \(n\).
Na standardni izlaz ispisati niz nakon iscrpne primene brisanja cifara.
10 2 3 1 0 0 1 0 1 0 0 1 1
1 1 0
U ovom bloku se opisuje glavno rešenje zadatka.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, k1, k2; cin >> n >> k1 >> k2;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> digit;
vector<int> count;
for (int i = 0; i < n; i++) {
if (digit.empty()) {
digit.push_back(a[i]);
count.push_back(1);
} else if (a[i] != digit.back()) { // !digit.empty()
if ((digit.back() == 0 && count.back() >= k1) ||
(digit.back() == 1 && count.back() >= k2)) {
digit.pop_back();
count.pop_back();
if (!digit.empty()) {
count.back()++;
}
} else {
digit.push_back(a[i]);
count.push_back(1);
}
} else { // !digit.empty() && a[i] == digit.back()
count.back()++;
}
}
if((digit.back() == 0 && count.back() >= k1) ||
(digit.back() == 1 && count.back() >= k2)) {
digit.pop_back();
count.pop_back();
}
for (int i = 0; i < digit.size(); i++) {
for (int j = 0; j < count[i]; j++) {
cout << digit[i] << " ";
}
}
cout << endl;
return 0;
}