Cod sursa(job #938352)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 12 aprilie 2013 14:05:54
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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];

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

bool u[nmax+1];

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

    int sol= inf;
    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=n; ++j){
            u[j]= (v[j]==o[j]);
        }

        int sol_aux= 0;
        for (int j= 1; j<=n; ++j){
            if (v[j]!=o[j]){
                for (int k= 1; k<=n; ++k){
                    if (v[j]==o[k]&& u[k]==0){
                        sol_aux+= base_cost*2+dist(j, k);
                        u[k]= 1;
                        break;
                    }
                }
            }
        }
        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;
}