Cod sursa(job #347368)

Utilizator savimSerban Andrei Stan savim Data 11 septembrie 2009 21:52:29
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX_N 610
#define inf 2147000000

int n, add, sol, val;
int A[MAX_N], B[MAX_N], ind[MAX_N], nr[MAX_N];
int poz[MAX_N], el[MAX_N];

void cit() {
    freopen("barman.in", "r", stdin);
	freopen("barman.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &A[i]);
		B[i] = A[i];
	}
	
	sort(B + 1, B + n + 1);
}    

void perm() {
	int aux = A[1];
	for (int i = 1; i < n; i++) A[i] = A[i + 1];
	A[n] = aux;
}

void solve() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (A[j] == B[i])
            	nr[i]++;

	sol = inf;
    for (int k = 1; k <= n; k++) {
		int last = 1;
		val = 0;

		for (int i = 1; i <= n; i++)
			if (B[i] != B[i - 1]) {
            	//voi pune cele nr[t] elemente pe pozitiile last..last + nr[i] - 1
            	poz[0] = el[0] = 0;
            	for (int j = last; j <= last + nr[i] - 1; j++)
					if (A[j] != B[i])
						poz[++poz[0]] = j;

				for (int j = 1; j <= n; j++)
					if (A[j] == B[i] && (j < last || last + nr[i] - 1 < j))
						el[++el[0]] = j;

				last = last + nr[i];          

				add = inf;
				for (int j = 0; j <= el[0]; j++) {
					int aux = 0, x = 0;
					
					x = poz[0];
					for (int p = 1; p <= j; p++) {
						aux += abs(el[p] - poz[x]) + 20;
						x--;
					}

					x = 1;
					for (int p = j + 1; p <= el[0]; p++) {
                    	aux += abs(el[p] - poz[x]) + 20;
						x++;
					}

					if (aux < add) add = aux;
				}
				val += add;
			}

		if (val < sol) sol = val;
		perm();
	}

	printf("%d\n", sol);		
}

int main() {

	cit();
	solve();

	return 0;
}