Телефонные номера, которые набираются на кнопочном телефоне ходом коня

/////////////////////////////////////////////////////////////////////////////////////////
//ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
//
//ХОД КОНЕМ
//(Время: 1 сек. Память: 16 Мб)
//Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, 
//которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается 
//телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
//
//Требуется написать программу, определяющую количество телефонных номеров длины N, 
//набираемых ходом коня.
//
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит натуральное число N (N <= 100).
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//В выходной файл OUTPUT.TXT выведите искомое количество телефонных номеров.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef unsigned long long  T_ull;
typedef std::string         T_str;
/////////////////////////////////////////////////////////////////////////////////////////
const   T_ull   MAX_ULL             =   std::numeric_limits<T_ull>::max();
const   int     TEL_NUM_LEN_MAX     =   103;
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T >
T_str   to_str( T   val )
{
    std::ostringstream  sout;
    sout    <<  val;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_big_int
{
    //-----------------------------------------------------------------------------------
    static  const   T_ull   FACTOR  =   T_ull(1e18);
    //-----------------------------------------------------------------------------------
    bool    is_overflow_;
    T_ull   head_;
    T_ull   tail_;
    //-----------------------------------------------------------------------------------
    friend  std::ostream    &   operator<<
        (
            std::ostream        &   os,
            T_big_int   const   &   big_int
        )
    {
        if( big_int.is_overflow_ )
        {
            os  <<  "overflow";
        }
        else
        {
            int     num_len     =   0;
            T_str   head_str    =   to_str( big_int.head_ );
            T_str   tail_str    =   to_str( big_int.tail_ );
 
            if( big_int.head_ > 0 )
            {
                num_len     +=  head_str.size();
                os          <<  head_str;
            }
 
            num_len     +=  tail_str.size();
 
            os          <<  tail_str
                        <<  std::endl
                        <<  "count_len = "
                        <<  num_len;
        }//else
 
        return  os;
    }
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_big_int( T_ull    ull = 0 )
        :
        is_overflow_    (),
        head_           (),
        tail_           ( ull )
    {
        normalize();
    }
    //-----------------------------------------------------------------------------------
    T_big_int   &   operator+=  ( T_big_int     const   &   i )
    {
        is_overflow_    =       is_overflow_
                            ||  i.is_overflow_;
 
        if( !is_overflow_ )
        {
            if( head_ > MAX_ULL - i.head_ )
            {
                is_overflow_    =   true;
            }
            else
            {
                head_   +=  i.head_;
                tail_   +=  i.tail_;
            }
 
            normalize();
        }//if
 
        return  *this;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    normalize()
    {
        if( !is_overflow_ )
        {
            T_ull   head_delta  =  tail_ / FACTOR;
 
            if( head_delta > MAX_ULL - head_ )
            {
                is_overflow_    =   true;
            }
            else
            {
                head_   +=  head_delta;
                tail_   %=  FACTOR;
            }//else
        }//if
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int     count_tel_numbers[10][TEL_NUM_LEN_MAX]    =   {0};
/////////////////////////////////////////////////////////////////////////////////////////
int     prev_digits_for[10][3]  =   {
                                        { 4,    6,  -1  },  //0
                                        { 6,    8,  -1  },  //1
                                        { 7,    9,  -1  },  //2
 
                                        { 4,    8,  -1  },  //3
                                        { 0,    3,  9   },  //4
                                        { -1,   -1, -1  },  //5
 
                                        { 0,    1,  7   },  //6
                                        { 2,    6,  -1  },  //7
                                        { 1,    3,  -1  },  //8
 
                                        { 2,    4,  -1  }   //9
                                    };
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int   get_count_tel_numbers_val
    (
        int     first_digit,
        int     num_len_cur
    )
{
    T_big_int   res     =   0;
 
    for( int  j = 0; j < 3; ++j )
    {
        int     prev_digit  =   prev_digits_for[ first_digit ][ j ];
 
        if  (
                prev_digit >= 0
            )
        {
            res     +=  count_tel_numbers[ prev_digit ][ num_len_cur - 1 ];
        }//if
    }//for
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int   count_tel_numbers_with_len( int     num_len )
{
    for( int  num_len_cur = 1; num_len_cur <= num_len; ++num_len_cur )
    {
        for( int  first_digit = 0; first_digit < 10; ++first_digit )
        {
            if( num_len_cur == 1 )
            {
                count_tel_numbers[first_digit][num_len_cur] = 1;
            }
            else
            {
                count_tel_numbers[first_digit][num_len_cur]     =   get_count_tel_numbers_val
                                                                        (
                                                                            first_digit,
                                                                            num_len_cur
                                                                        );
            }//else
        }//for
    }//for
 
    T_big_int   res     =   0;
 
    for( int  first_digit = 0; first_digit < 10; ++first_digit )
    {
        if  (
                    first_digit     !=  0
                &&  first_digit     !=  8
            )
        {
            res     +=  count_tel_numbers[ first_digit ][ num_len ];
        }//if
    }//for
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T >
void    print_prompt_and_input_val_in_segment
    (
        T_str   const   &   prompt,
        T               &   val,
        T                   left_bound,
        T                   right_bound
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val             <   left_bound
                ||  right_bound     <   val
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        int     num_len     =   0;
        T_str   prompt      =       T_str( "Phone number length (" )
                                +   to_str( 1 )
                                +   ".."
                                +   to_str( TEL_NUM_LEN_MAX )
                                +   "): ";
 
        print_prompt_and_input_val_in_segment
            (
                prompt,
                num_len,
                1,
                TEL_NUM_LEN_MAX
            );
 
        std::cout   <<  count_tel_numbers_with_len( num_len )
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}

int level = 20;
    unsigned long long sum = 0;
    char init[][3] = { { 4, 5, -1 }, { 5, 7, -1 }, { 6, 8, -1 }, { 4, 7, -1 }, { 3, 8, 0 }, { 1, 6, 0 }, { 2, 5, -1 }, { 1, 3, -1 }, { 2, 4, -1 } };
    unsigned long long data[2][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 0}};
    for (int d = 1; d < 9; d = (d + 1 == 7) ? d + 2 : d + 1) {
        data[0][d] = 1;
        for (int k = 1; k < level; k++) {
            for (int di = 0; di < 9; di++) {
                data[1][di] = data[0][di];
                data[0][di] = 0;
            };
            for (int i = 0; i < 9; i++)
                if (data[1][i] != 0)
                    for (int ci = 0; ci < ((i == 4 || i == 5) ? 3 : 2); ci++) data[0][init[i][ci]] += data[1][i];
        }
        for (int di = 0; di < 9; di++) {
            sum += data[0][di];
            data[0][di] = 0;
        }
    };
    printf("%i", sum);