Cod sursa(job #347292)

Utilizator CezarMocanCezar Mocan CezarMocan Data 11 septembrie 2009 18:22:42
Problema Barman Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 627
#define inf 1000000027

using namespace std;

int n, i, j, sol, cost, aux;
int s[maxn], v[maxn], x[2 * maxn], c[maxn], cup[maxn];

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++) {
			if (!cup[i] && c[i] != s[i]) {
				int nod = c[i]; int poz = i; 
				do {
					for (j = 1; j <= n; j++)
						if (s[j] == nod && !cup[j])
							break;
					cup[j] = 1;
					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;
}