Cod sursa(job #526556)

Utilizator AndreyPAndrei Poenaru AndreyP Data 28 ianuarie 2011 17:16:39
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 610

int n;
int a[N],v[N],b[N];
int vrea[N][N];
int are[N][N];
int szVrea[N],szAre[N];
int rez = N*N*N;

inline void citire() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
		v[i] = a[i];
	}
}

inline int caut(int x) {
	if(v[1]==x)
		return 1;
	if(v[v[0]]==x)
		return v[0];

	int p=1,u=v[0],m;

	while(p<u) {
		m = (p+u)>>1;

		if(x<=v[m])
			u = m;
		else
			p = m+1;
	}

	return p;
}

inline void precalc() {
	sort(v+1,v+n+1);
	v[0] = 1;
	for(int i=2; i<=n; ++i) {
		if(v[v[0]]!=v[i])
			v[++v[0]] = v[i];
	}

	for(int i=1; i<=n; ++i) {
		a[i] = caut(a[i]);
		b[i] = a[i];
	}

	sort(b+1,b+n+1);
}

inline int modul(int x) {
	return ( (x<0) ? (-x) : (x) );
}
	
inline void rezolva() {
	int n1 = n+1;
	int rez1;

	for(int i=1; i<=n; ++i) {
		rez1 = 0;
		memset(szVrea,0,sizeof(szVrea));
		memset(szAre,0,sizeof(szAre));

		for(int j=i,t=1; t<=n; ++t,++j) {
                	if(j==n1)
				j = 1;

                        if(a[t]!=b[j]) {
				++rez1;
                        	are[a[t]][++szAre[a[t]]] = t;
				vrea[b[j]][++szVrea[b[j]]] = t;
			}
		}

		rez1 *= 20;
                for(int j=1; j<=v[0]; ++j) {
			for(int t=1; t<=szAre[j]; ++t)
				rez1 += modul(vrea[j][t]-are[j][t]);
		}

                if(rez1<rez)
			rez = rez1;
	}
}

int main() {
	freopen("barman.in","r",stdin);
	freopen("barman.out","w",stdout);

        citire();
	precalc();
	rezolva();

	printf("%d\n",rez);
	return 0;
}