Cod sursa(job #211256)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 1 octombrie 2008 16:52:24
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <algorithm>
#define inf 100000000
using namespace std;
long n,i,j,t,aux,a[601],b[601],mark[601];
long poz,c,cmin,ctotal,ctotalmin;

int main(){
    freopen("barman.in","r",stdin);
    freopen("barman.out","w",stdout);
    scanf("%ld\n",&n);
    ctotalmin=inf;
    for (i=1;i<=n;++i) {scanf ("%ld",&a[i]);b[i]=a[i];}
    sort(b+1,b+n+1);
    for (t=0;t<n;++t){
        if (t){aux=b[1];for (i=1;i<n;++i)b[i]=b[i+1]; b[n]=aux;}
        for (i=1;i<=n;++i)mark[i]=0;
        ctotal=0;
        for (i=1;i<=n;++i)
            if (b[i]!=a[i]){
               cmin=inf;
               for (j=1;j<i;++j)
                   if (!mark[j]&&a[j]==b[i]){
                      c=min(n-i+j,i-j);
                      if (c<cmin){cmin=c;poz=j;}
                   }
               for (j=i+1;j<=n;++j)
                   if (!mark[j]&&a[j]==b[i]){
                      c=min(n-j+i,j-i);
                      if (c<cmin){cmin=c;poz=j;}
                   }
               ctotal+=20+cmin;
               mark[poz]=1;
            }
        if (ctotal<ctotalmin)ctotalmin=ctotal;
    }
    printf("%ld\n",ctotalmin);
return 0;
}