Cod sursa(job #771600)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 26 iulie 2012 15:54:00
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <algorithm>

using namespace std;


const int N = 605;

int n, minim = 0x3f3f3f3f;
int p[N], sortat[N], op[N];

int abs(int a)
{
    if (a < 0)
        return -a;
    return a;
}

void initializeaza(int a[], int n)
{
    for (int i = 1; i <= n; ++i)
        a[i] = 0;
}

void perm(int a[], int n)
{
    int aux = a[1];
    for (int i = 1; i < n; ++i)
        a[i] = a[i + 1];
    a[n] = aux;
}

int timp(int a[], int b[], int op[], int n)
{
    int t = 0;
    for(int i = 1; i <= n; ++i)
        if(a[i] == b[i])
            op[i] = a[i];
    for (int i = 1; i <= n; ++i) {
        if(a[i] == b[i])
            continue;
        for (int j = 1; j <= n; ++j) {
            if (a[i] == b[j] && !op[j]) {
                t += abs(i - j) + 20;
                op[j] = a[i];
                break;
            }
        }
    }

    return t;
}

int main()
{
    freopen ("barman.in", "r", stdin);
    freopen ("barman.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);
        sortat[i] = p[i];
    }

    sort(sortat + 1, sortat + n + 1);
    for (int i = 1; i <= n; ++i) {
        initializeaza(op, n);
        minim = min(minim, timp(p, sortat, op, n));
        perm(sortat, n);
    }
    
    printf("%d", minim);

    return 0;
}