Cod sursa(job #235)

Utilizator gcosminGheorghe Cosmin gcosmin Data 7 decembrie 2006 17:34:19
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define NMAX 610

inline int MIN(int a, int b) { return (a < b) ? a : b; }
inline int ABS(int x) { return (x < 0) ? -x : x; }

int N;

int a[NMAX];
int b[NMAX];
int c[NMAX];
char viz[NMAX];

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

	scanf("%d", &N);

	for (i = 1; i <= N; i++) scanf("%d", &a[i]);

	memcpy(b, a, sizeof(a));

	sort(b + 1, b + N + 1);

	int sol = 1000000000;
	int val = 0;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++) c[j] = val, viz[j] = 0;

		for (j = 1; j <= N; j++)
			if (a[j] == b[j]) c[j] = a[j], viz[j] = 1;;

		int rez = 0;
		for (j = 1; j <= N; j++)
		{
			if (viz[j]) continue;
			for (k = 1; k <= N; k++)
				if (a[j] == b[k] && c[k] == val)
				{
					rez += 20 + ABS(j - k);
					c[k] = a[j];
					break;
				}				
		}

		if (rez < sol) sol = rez;

		int aux = b[N];
		for (j = N; j > 1; j--) b[j] = b[j-1];
		b[j] = aux;


	}

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


fclose(stdin);
fclose(stdout);
return 0;
}