#
/*program string ABC */
#include <iostream>
#include <string>
#include <conio.h>
#include <cstdio>
#include <iomanip>
using namespace std;
 
const int maxx = 100;
int N, MinC;
char X[maxx], Best[maxx];
int T[maxx]; /*T[i] cho biet so kí tu "C" trong doan tù X[1] -> X[i]*/
/*Hàm Same (i, L ) cho biet xau gòm 1 kí tu ket thuc tai X[i] có trùng vói xau
1 kí tu lien truoc nó hay ko*/

bool Same ( int i, int L )
{
        int j = i - L; /*j là vi trí cuoi doan lien truoc doan dó*/
        for ( int k = 0; k < L; k++ )
        {
                if ( X[i-k] != X[j-k] )
                {
                        return false;
                }
        }
        return true;
}

/*Hàm Check cho biet X[i] có làm hong tính lap cua dãy X[1..i] hay không*/
bool Check ( int i )
{
        for ( int L = 1; L <= i/2; L++ ) /*Thu các do dài L*/
        {
                if ( Same (i,L)== true ) /*Néu có xau do dài L ket thúc boi X[i] bi
                                  trùng vói xâu lièn truóc*/
                {
                        return false;
                }
        }
        return true;
}

/*Giu lai két qua tìm dc vào BestConfig ( MinC và mãng Best )*/
void KeepResult()
{
        MinC = T[N];
        for ( int i = 0; i <= N; i++ )
        {
                Best[i] = X[i];
        }
}

/*Thuat toán quay lùi nhánh can*/
void Branch_Bound ( int i )
{
        char j;
        for ( j = 'A'; j <= 'C'; j++ )
        {
                X[i] = j;
                if ( Check(i) == true ) /*Néu them giá tri vào dó ko làm hong tính lap*/
                {
                        if ( (T[i] + (N-i)/4 ) < MinC ) /*Dánh giá*/
                        {
                            if ( j == 'C' )
                            {
                                    T[i] = T[i-1] + 1; /*Tính T[i] qua T[i-1]*/
                            }
                            else
                            {
                                    T[i] = T[i-1];
                            }
                            if ( i == N ) KeepResult();
                            else          Branch_Bound(i + 1);
                        }
                }
        }
}

void PrintResult()
{
        for ( int i = 1; i <= N; i++ )
        {
                cout << Best[i];
        }
        cout << endl;
        cout <<  " Minimum letter C : " << MinC << endl;
}       

int main()
{
        cout << "Enter the length of string "; cin >> N;
        T[0] = 0;
        MinC = N;
        Branch_Bound(1);
        PrintResult();
        system("pause");
        return 0;
}