Cod sursa(job #199361)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 18 iulie 2008 09:23:34
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
long n,i,a[1201],b[601],m,j,c[601],*d,e[601],f[601],
g[601][601],h[601][601],sol=2000000000;
void citire();
void sortare();
void normalizare();
void solve();
void afisare();
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}
void citire()
{
	freopen("barman.in","rt",stdin);
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
	{ scanf("%ld",&a[i]);
	  a[i]-=2000000000;
	}
	normalizare();
	sortare();
	for(i=1;i<=n;i++)a[i+n]=a[i];
}
void sortare()
{
	n=0;
	for(i=1;i<=m;i++)
	 for(j=1;j<=c[i];j++)
	  b[++n]=i;
}
void normalizare()
{
	long L=1,R=n,min;
	while(L<=R)
	{  min=1;
	   for(i=L;i<=R;i++)
	    min=(a[i]<min)?a[i]:min;
	   if(min==1)return;
	   m++;
	   while(a[L]==min){a[L]=m;L++;c[m]++;}
	   while(a[R]==min){a[R]=m;R--;c[m]++;}
	   for(i=L;i<=R;i++)
	    if(a[i]==min){a[i]=m;c[m]++;}
	}
}
void solve()
{ long k,sc,mici;
  for(i=1;i<=n;i++)
  { d=&a[i-1];
    for(j=1;j<=m;j++){e[j]=0;f[j]=0;}
    for(j=1;j<=n;j++)
     { if(b[j]==d[j])continue;
       g[b[j]][++e[b[j]]]=j;
       h[d[j]][++f[d[j]]]=j;
     }
    sc=0;
    for(j=1;j<=m;j++)
    { if(!e[j])continue;
      sc+=20*e[j];mici=0;
      for(k=1;k<=e[j];k++)
      { if(h[j][k]<g[j][1]){sc-=h[j][k];mici++;}
	else sc+=h[j][k];
      }
      for(k=1;k<=mici;k++)
       sc+=g[j][k];
      for(k=mici+1;k<=e[j];k++)
       sc-=g[j][k];
    }
    sol=(sol<sc)?sol:sc;
  }
}
void afisare()
{
	freopen("barman.out","wt",stdout);
	printf("%ld\n",sol);
}