Cod sursa(job #594605)

Utilizator rudarelLup Ionut rudarel Data 8 iunie 2011 15:24:14
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
#define NMAX 610
 
inline int MIN(int a, int b) { return (a < b) ? a : b; }
inline int ABS(int x) { return (x < 0) ? -x : x; }
 
int N;
 
int a[NMAX];
int b[NMAX];
int c[NMAX];
char viz[NMAX];
 
int main()
{
    int i, j, k;
     
    freopen("barman.in", "r", stdin);
    freopen("barman.out", "w", stdout);
 
    scanf("%d", &N);
 
    for (i = 1; i <= N; i++) scanf("%d", &a[i]);
 
    memcpy(b, a, sizeof(a));
 
    sort(b + 1, b + N + 1);
 
    int sol = 1000000000;
    int val = 0;
    for (i = 1; i <= N; i++)
    {
        for (j = 1; j <= N; j++) c[j] = val, viz[j] = 0;
 
        for (j = 1; j <= N; j++)
            if (a[j] == b[j]) c[j] = a[j], viz[j] = 1;;
 
        int rez = 0;
        for (j = 1; j <= N; j++)
        {
            if (viz[j]) continue;
            for (k = 1; k <= N; k++)
                if (a[j] == b[k] && c[k] == val)
                {
                    rez += 20 + ABS(j - k);
                    c[k] = a[j];
                    break;
                }              
        }
 
        if (rez < sol) sol = rez;
 
        int aux = b[N];
        for (j = N; j > 1; j--) b[j] = b[j-1];
        b[j] = aux;
 
 
    }
 
    printf("%d\n", sol);
 
 
fclose(stdin);
fclose(stdout);
return 0;
}