Cod sursa(job #658520)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 8 ianuarie 2012 23:18:58
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int v[601],v2[601],c[601],d[601],x[601];

int main()
{
	int i,j,n,t,aux,sol=2000000000;

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

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

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

	for (t=1;t<=n;++t)
	{
	    aux=0;
		memset(x,0,sizeof(x));
		memset(d,0,sizeof(d));

		for (i=1,j=t;i<=n;++i,++j)
		{
			if (j>n)
                j=1;
			c[i]=v2[j];
		}

		for (i=1;i<=n;++i)
			if (v[i]==c[i])
			{
				d[i]=i;
				x[i]=1;
			}

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

		memset(x,0,sizeof(x));
        memcpy(c,v,sizeof(v));

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

		if (aux<sol)
			sol=aux;
	}

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