Cod sursa(job #53521)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 22 aprilie 2007 13:45:32
Problema Barman Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <algorithm>
#include <string>
#include <stdlib.h>

using namespace std;

#define maxn 610
#define maxv 1000000000

int n,sol,rez;
int a[maxn],b[maxn],used[maxn],v[maxn];

int main()
{
    freopen("barman.in","r",stdin);
    freopen("barman.out","w",stdout);
    
    int i,j,x,k,p,y;
    scanf("%d ",&n);
    
    for (i=0;i<n;i++) 
    {
        scanf("%d ",&a[i]);
        b[i]=a[i];
    }
    
    sort(b,b+n);
    sol=maxv;
    
    for (i=0;i<n;i++)
    {
        memset(used,0,sizeof(used));
        memset(v,0,sizeof(v));
        rez=0;
        for (j=0;j<n;j++) 
          if (a[j]==b[(i+j)%n]) 
          {
              used[j]=1;
              v[(i+j)%n]=1;
          }
          
        for (j=0;j<n;j++)
          if (!used[j]) 
          {
               x=maxn;
               y=i-1;
               for (k=0;k<n;k++)
               {
                   y++;
                   if (y==n) y=0;
                   if ((a[j]==b[y]) && (!v[y]) && (abs(j-k)<x)) 
                   {
                         p=y;
                         x=abs(j-k);
                   }
               }
               
//               printf("%d %d\n",x,p);
               v[p]=1;
               used[j]=1;
               rez+=20+x;
          }
          
//        printf("%d\n",rez);
          
        if (rez<sol) sol=rez;
    }
    
    printf("%d\n",sol);
    
    return 0;
}