Cod sursa(job #1327418)

Utilizator nicolaegutaNicolae Guta nicolaeguta Data 26 ianuarie 2015 18:30:38
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <algorithm>
#define Nmax 605
#define INF 2000000000

using namespace std;

struct el
{
    int val,poz;
    bool operator <(const el &A) const
    {
        if(val==A.val) return poz<A.poz;
        return val<A.val;
    }
} kkt[Nmax];
int a[Nmax],v[Nmax],n,viz[Nmax];

inline void Normalize()
{
    int i;
    sort(kkt+1,kkt+n+1);
    for(i=1;i<=n;++i) v[kkt[i].poz]=i;
}

int main()
{
    int sol=INF,i,poz,val,p,copie,cost;
    freopen ("barman.in","r",stdin);
    freopen ("barman.out","w",stdout);
    scanf("%d", &n);
    for(i=1;i<=n;++i) scanf("%d", &a[i]);
    for(i=1;i<=n;++i) a[n+i]=a[i];
    for(p=1;p<=n;++p)
    {
        cost=0;
        for(i=p;i<=p+n-1;++i)
        {
            v[i-p+1]=a[i];
            kkt[i-p+1].val=a[i]; kkt[i-p+1].poz=i-p+1;
        }
        Normalize();
        for(i=1;i<=n;++i)
            viz[i]=0;
        for(i=1;i<=n;++i)
            if(viz[i]<2 && v[i]!=i)
            {
                poz=i; val=v[poz]; cost+=10; v[poz]=-1;
                while(viz[poz]<2 && val!=poz)
                {
                    ++viz[poz]; copie=v[val]; v[val]=val;
                    cost+=min(abs(val-poz),n-max(val,poz)+min(val,poz));
                    if(copie==-1) cost+=10;
                    else cost+=20;
                    poz=val; val=copie;
                    if(val==-1) break;
                    //printf("%d %d %d\n", poz,val,cost);
                }
            }
        sol=min(sol,cost);
    }
    printf("%d\n", sol);
    return 0;
}