Cod sursa(job #907342)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 7 martie 2013 21:12:10
Problema Barman Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int inf= 1<<30;
const int nmax= 600;
const int base_cost= 10;

int v[nmax+1];
int o[nmax+1];

struct v_cmp{
    bool operator ()(int x, int y){
        if (v[x]!=v[y]){
            return v[x]<v[y];
        }else{
            return x<y;
        }
    }
};

int n;
inline int dist(int x, int y){
    if (x<y){
        return min(y-x, n+x-y);
    }else{
        return min(x-y, n+y-x);
    }
}

int main(){
    fin>>n;
    for (int i= 1; i<=n; ++i){
        fin>>v[i];
    }
    for (int i= 1; i<=n; ++i){
        o[i]= i;
    }
    sort(o+1, o+n+1, v_cmp());

    int sol= inf;
    for (int i= 1; i<=n; ++i){
        int sol_aux= 0;
        for (int j= 1; j<=n; ++j){
            if (o[j]!=j){
                sol_aux+= 2*base_cost+dist(j, o[j]);
            }
        }
        if (sol>sol_aux){
            sol= sol_aux;
        }

        int aux= o[1];
        for (int j= 1; j<n; ++j){
            o[j]= o[j+1];
        }
        o[n]= aux;
    }
    fout<<sol<<"\n";

    return 0;
}