Cod sursa(job #902789)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 1 martie 2013 16:43:14
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <algorithm>
#define NMax 610
using namespace std;

const char IN[]="barman.in",OUT[]="barman.out";

int N,L,Rez=(1<<30);
int v[NMax],s[NMax],o[NMax];

int dist(int x,int y)
{
    if (x>y) swap(x,y);
    return min(y-x,N-y+x);
}

void rotate()
{
    int i,x;
    x=s[1];
    for (i=2;i<=N;++i) s[i-1]=s[i];
    s[N]=x;
}

int solve()
{
    int i,ret=0;
    for (i=1;i<=N;++i) o[i]=0;

    for (i=1;i<=N;++i)
        if (v[i]==s[i])
            o[i]=true;

    for (i=1;i<=N;++i)
    {
        if (v[i]==s[i]) continue;
        for (int j=1;j<=N;++j)
            if (v[i]==s[j] && !o[j])
            {
                ret+= 20+abs(i-j);
                o[j]=true;
                break;
            }
    }
    return ret;
}

int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%d",&N);
    for (i=1;i<=N;++i) scanf("%d",v+i),s[i]=v[i];
    fclose(stdin);

    sort(s+1,s+N+1);

    for (int j=1;j<=N;++j)
    {
        if (j!=1) rotate();
        Rez=min(Rez,solve());
    }

    freopen(OUT,"w",stdout);
    printf("%d\n",Rez);
    fclose(stdout);

    return 0;
}