Cod sursa(job #743722)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 5 mai 2012 16:50:51
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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;
}