Cod sursa(job #349368)

Utilizator raduzerRadu Zernoveanu raduzer Data 19 septembrie 2009 11:33:01
Problema Barman Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 610;
const int INF = 0x3f3f3f3f;

int n,  sol;
int a[MAX_N], b[MAX_N], c[MAX_N], f[MAX_N], d[MAX_N];

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

	scanf("%d", &n);

	for (i = 1; i <=n; ++i)
	{
		scanf("%d", &a[i]);
		b[i] = a[i];
	}

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

	sol = INF;

	for (t = 1; t <= n; ++t)
	{
		memset(f, 0, sizeof(f));
		for (i = 1, j = t; i <= n; ++i, ++j)
		{
			if (j > n) j = 1;
			c[i] = b[j];
		}

		int cost = 0;

		for (i = 1; i <= n; ++i)
			for (j = 1; j <= n; ++j)
				if (a[i] == c[j] && !f[j])
				{
					d[i] = j;
					f[j] = 1;
					break;
				}

		memcpy(c, a, sizeof(a));
		memset(f, 0, sizeof(f));

		for (i = 1; i <= n; ++i)
			if (!f[i])
			{
				if (d[i] == i) continue;
				int j = i;
				while (!f[j])
				{
					cost += 20 + abs(d[j] - j);
					f[j] = 1;
					j = d[j];
				}
			}

		if (cost < sol)
			sol = cost;
	}

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