Cod sursa(job #347257)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 11 septembrie 2009 17:20:22
Problema Barman Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

#define maxn 610

long n, i, j, k, poz, c1, c2, sol, cost, v[maxn], s[maxn], c[maxn];

long min(long a, long b)
{
    if(a<b) return a;
    return b;
}

int main()
{
    freopen("barman.in", "r", stdin);
    freopen("barman.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &v[i]);
        s[i]=v[i];
    }
    sort(s+1, s+n+1);
    sol=2000000000;
    for(i=1; i<=n; i++)
    {
        cost=0;
        memset(c, 0, sizeof(c));
        for(j=1; j<=n; j++)
        {
            if(s[j]==v[j]) c[j]=1;
        }
        for(j=1; j<=n; j++)
        {
            if(s[j]!=v[j])
            {
                for(k=1; s[k]!=v[j] || c[k]; k++);

                c[k]=1;
                if(k<j)
                {
                    c1=k;
                    c2=j;
                }
                else
                {
                    c1=j;
                    c2=k;
                }
                cost=cost+20+min(c2-c1, n-c2+c1);
            }
        }
        if(cost<sol)
        {
            poz=i;
            sol=cost;
        }
        for(j=0; j<n; j++)
        {
            s[j]=s[j+1];
        }
        s[n]=s[0];
    }
    printf("%d\n", cost);
    return 0;
}