Cod sursa(job #1678189)

Utilizator sucureiSucureiRobert sucurei Data 7 aprilie 2016 09:00:36
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;

ifstream in("barman.in");
ofstream out("barman.out");

const int N = 602;

int v[N],vs[N],p[N],u[N],ver[N],costMin = 1<<25,cost,n;

inline int m(const int &q) {
    return q>0 ? q : -q;
}

int main() {
    int i,j,k;

    in >> n;

    for(i = 1; i<=n; ++i) {
        in >> v[i];
        vs[i] = v[i];
    }

    sort(vs + 1, vs + n + 1);

    for(k = 1; k<=n; ++k) {

        for(i = 1, j = k; i<=n; ++i, ++j) {
            if(j > n)
                j=1;
            p[j] = vs[i];
        }

        memset(u,0,sizeof(u));
        memset(ver,0,sizeof(ver));

        for(i = 1; i<=n; ++i)
            if(v[i] == p[i]) {
                u[i] = i;
                ver[i] = 1;
            }

        for(i = 1; i<=n; ++i) if(!u[i])
            for(j = 1; j<=n; ++j) if(!ver[j] && v[i] == p[j]) {
                u[i] = j;
                ver[j] = 1;
                break;
            }

        memset(ver, 0, sizeof(ver));
        cost = 0;

        for(i = 1; i<=n; ++i) if(!ver[i] && u[i] != i) {
            j = i;
            while(!ver[j]) {
                cost += 20 + m(u[j] - j);
                ver[j] = 1;
                j = u[j];
            }
        }

        if(cost < costMin)
            costMin = cost;
    }

    out << costMin << "\n";

    return 0;
}