ИТМО_отбор_dp

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define pb(x) push_back(x)
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}
int N;

bool sh=1;

void cvp(vector <pii> a){
    for (auto p: a){
        cout<<p.first<<' '<<p.second<<"\n";
    }
    cout<<"\n";
}

string to(int x){
    string r="";
    while (x > 0){
        r += x%2+'0';
        x/=2;
    }
    reverse(r.begin(), r.end());
    while (r.size() < N){
        r = '0' + r;
    }
    return r;
}

bool log(bool a, bool b, bool c){
    return !b || a&&c || (!a)&&(!c);
}

bool ok(string s){
    if (sh) cout<<s<<"\n";
    int n = s.size();
    for (int i = 0; i < n - 2; ++i){
        bool a,b,c;
        a = s[i]-'0';
        b=s[i+1]-'0';
        c = s[i+2]-'0';
        if (log(a,b,c) ){
            if (s[i+2] != s[n-1]) continue;
            else {
            if (sh) cout<<"OK\n";
               return 1;
            }
        }
        else{
            if (sh) cout<<"NO\n";
            return 0;
        }
    }
}

int f(int n){
    int ans=0;
    if (sh){
        cout<<"n = "<<n<<"\n";
    }
    for (int i = 0; i < pow(2, n); ++i){
        string s = to(i);
        if (ok(s))ans++;
    }
    return ans;
}

int main()
{
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    /*int n=10;
    N=n;
    while (f(n) != 611 &&n <11){
        if (sh){
            cout<<"n = "<<n<<"\n";
            cout<<f(n)<<"\n";
        }
        n++;
        N=n;
    }*/
    vector <vector<int>> dp(20, vector <int> (6));
    for (int i = 0; i < 6; ++i) dp[3][i] = 1;
    int i = 3;
    while (1){
        int s=0;
        for (int j = 0; j < 6; ++j) s += dp[i][j];
        if (s == 611){
            cout<<"ans = "<<i<<"\n";
            break;
        }
        i++;
        dp[i][0] = dp[i - 1][0] + dp[i - 1][3];
        dp[i][1] = dp[i][0];
        dp[i][2] = dp[i-1][1] + dp[i-1][4];
        dp[i][3] = dp[i-1][2];
        dp[i][4] = dp[i][3];
        dp[i][5] = dp[i-1][5];
    }

    //cout<<n;
}