# include < iostream >
# include < cstring >
using namespace std ;
typedef int stiva[ 100 ];
int n; // numarul de litere din secventa
char a[ 4 ] = { 'A' , 'B' , 'C' , 'D' }; // mulțimea de litere
char b[ 100 ]; // secvența curentă
stiva st; // stiva de selectie
// initializare stiva
void init ( int k) {
st[k] = 0 ;
}
// functia de generare a succesorilor
int succesor ( int k) {
if (st[k] < 3 ) {
st[k]++;
return 1 ;
} else {
return 0 ;
}
}
// functia de verificare a solutiei
int solutie ( int k) {
return k == n;
}
// functia de verificare a validitatii solutiei partiale
int valid ( int k) {
// se verifică condiția ca două litere identice să nu fie una lângă alta
if (k > 1 && b[k - 1 ] == b[k]) {
return 0 ;
}
// se verifică condiția ca n/2 litere să fie A
int cnt_a = 0 ;
for ( int i = 1 ; i <= k; i++) {
if (b[i] == 'A' ) {
cnt_a ++;
}
}
if ( cnt_a > n / 2 ) {
return 0 ;
}
return 1 ;
}
// functia de afisare a solutiei
void tipar () {
for ( int i = 1 ; i <= n; i++) {
cout << b[i];
}
cout << endl ;
}
// functia de backtracking
void bt ( int k) {
init (k);
while ( succesor (k)) {
b[k] = a[st[k]];
if ( valid (k)) {
if ( solutie (k)) {
tipar ();
} else {
bt (k + 1 );
}
}
}
}
int main () {
// citirea datelor de intrare
cout << " Introduceti numarul de litere din secventa (n trebuie sa fie par): " ;
cin >> n;
// apelul functiei de backtracking
bt ( 1 );
return 0 ;
}