Cod sursa(job #53577)

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

using namespace std;

#define maxn 610
#define maxv 1000000000
#define min(a,b) ((a) < (b) ? (a) : (b))

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 (!v[(j+i)%n]) 
          {
                x=maxv;
                for (k=0;k<n;k++)
                  if ((!used[k]) && (a[k]==b[(i+j)%n]) && (min(abs(j-k),abs(n-j+k)<x)))
                  {
                      p=k;
                      x=min(abs(j-k),abs(n-j+k));
                  }
                  
                used[p]=1;
                v[(i+j)%n]=1;
                rez+=20+x;
          }
                    
        if (rez<sol) sol=rez;
    }
    
    printf("%d\n",sol);
    
    return 0;
}