Cod sursa(job #912525)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 14:48:56
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 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;
}