Cod sursa(job #211279)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 1 octombrie 2008 17:13:55
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <algorithm>
#define inf 100000000
#define minim(a,b) ((a)<(b)?(a):(b))
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]&&a[j]!=b[j]){
                      c=minim(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]&&a[j]!=b[j]){
                      c=minim(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;
}