СПБГУ_A_1

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
using namespace std;
/*
решение:
1)сделать граф
2)найти мин гамильтонов путь
3) ответ = мин гамильтонов путь + расстояние, чтобы дойти до стартовой вершины этого пути


ЕСЛИ ТАКОЕ НЕ ЗАЙДЁТ хотя бы на 90 баллов:
)посчитать за О(n^2), из какой вершины выгоднее стартовать = вершина start
)посчитать минимальные гамильтоновы пути из каждой вершины
)перебрать все сочетания за O(n) : (x, y), где x - длина пути до стартовой вершины, y - длина мин гамильтонова пути

*/
using ll = long long;
using ld = long double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n\n";
}
int N;
int inf = 1e9;
vector <int> a, b;
vector <vector <int>> G;
void cG(){
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            cout<<"("<<i+1<<","<<j+1<<") = "<<G[i][j]<<"\n";
        }cout<<"\n";
    }cout<<"\n";
}
int mk(int x, int y){
    int idx, idy, r = 0;
    for (int i=0;i<N;++i){
        if (a[i] == x){
            idx = i;
        }
        else if (a[i] == y){
            idy = i;
        }
    }
    r += abs(idx - idy);

    for (int i=0;i<N;++i){
        if (b[i] == x){
            idx = i;
        }
        else if (b[i] == y){
            idy = i;
        }
    }
    r += abs(idx - idy);
    return r;
}
vector <vector <int> > dp;
string two(int x){
    string r="";
    while (x > 0){
        r += ((x % 2) + 48);
        x /= 2;
    }

    while (r.size() != N){
        r += '0';
    }reverse(r.begin(), r.end());
    return r;
}

void wrk(){
    for (int msk = 1; msk < 1 << N; ++msk){
        cout<<"mask = "<<two(msk)<<"\n";
        for (int i = 0; i < N; ++i){
            if (msk & (1 << i) == 0) continue;
            for (int j = 0; j < N; ++j){
                if (msk && (1 << j) != 0) continue;
                dp[msk | (1 << j)][j] = min(dp[msk | (1 << j)][j], dp[msk][i] + G[i][j]);
            }
        }
    }
}

void cdp(){
    for (auto x: dp){
        for (auto y: x) cout<<y<<' ';
        cout<<"\n";
    }cout<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    G.resize(N, vector <int> (N, inf));
    a.resize(N, inf); b.resize(N, inf);
    for (int i = 0; i < N; ++i){
        int inb; cin>>inb; inb--;
        cout<<"inb = "<<inb<<"\n";
        a[i] = i;
        b[inb] = i;
    }
    cv(a);
    cv(b);
    for (int i = 0; i < N; ++i){
        for (int j = 0; j != i && j < N; ++j){
            G[i][j] = G[j][i] = mk(i, j);
        }
    }
    cG();
    //мин гамильтонов путь
    dp.assign(1<<N, vector <int> (N, inf));
    for (int i = 0; i < N; ++i){
        dp[1<<i][i] = 0;
    }
    wrk();
}
/*
5
1 3 5 2 4


6
3 6 4 1 5 2
*/