Cod sursa(job #347262)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 11 septembrie 2009 17:25:50
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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];

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]=2;
            else
                cost+=20;
        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+=c2-c1;
            }
        if(cost<sol)
            sol=cost;
        for(j=0; j<n; j++)
            s[j]=s[j+1];
        s[n]=s[0];
    }
    printf("%d\n", sol);
    return 0;
}