Cod sursa(job #347307)

Utilizator CezarMocanCezar Mocan CezarMocan Data 11 septembrie 2009 18:53:31
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define maxn 627
#define inf 1000000027

using namespace std;

int n, i, j, sol, cost, aux, nr;
int s[maxn], v[maxn], x[2 * maxn], c[maxn], cup[maxn], ac[maxn];
map <int, int> mp;

int main() {
	freopen("barman.in", "r", stdin);
	freopen("barman.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i++) 
		scanf("%d", &v[i]);
	
	memcpy(x, v, sizeof(v));
	
	sort(x + 1, x + n + 1);
	for (i = 1; i <= n; i++)
		x[i + n] = x[i];
	
	sol = inf;
	for (int q = 1; q <= n; q++) {
		memcpy(c, v, sizeof(v));
		memset(cup, 0, sizeof(cup));
		cost = 0;
		
		for (j = q; j <= n + q - 1; j++)
			s[j - q + 1] = x[j];
		for (i = 1; i <= n; i++) {
			mp[c[i]] = 0;
			if (c[i] == s[i])
				cup[i] = 1;
		}
		
		for (i = 1; i <= n; i++)
			if (!cup[i]) {
				mp[c[i]]++;
				ac[i] = mp[c[i]];
			}
		
		for (i = 1; i <= n; i++) {
			if (!cup[i]) {
				int nod = c[i]; int poz = i; 
				do {
					nr = 0;
					for (j = 1; j <= n; j++) {
						if (s[j] == nod && cup[j] != 1) 
							nr++;
						if (nr == ac[poz])
							break;
					}
					cup[j] = 2;
					aux = c[j]; c[j] = nod; nod = aux;
					cost += 20 + abs(poz - j);
					poz = j;
				} 
				while (poz != i);
				
			}
		}
		
		if (cost < sol)
			sol = cost;
	}		
	
	printf("%d\n", sol);
	
	return 0;
}